Solved

Big-Oh Proof

Posted on 2004-09-28
8
1,416 Views
Last Modified: 2012-06-21
I'm trying to prove, using the definition of big-Oh, that if we have two functions p(n) and q(n), and p(n) is O( q(n) ), then:

[a x p(n)] - [b x q(n)] is O( q(n) )     where a and b are constants.

Can anyone provide any ideas as to how to tackle this?
0
Comment
Question by:jshantz4
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
  • 2
  • +1
8 Comments
 
LVL 84

Accepted Solution

by:
ozo earned 500 total points
ID: 12178980
p(n) <= C*q(n) for n > n0
[a x p(n)] - [b x q(n)] <= (a*C-b)*q(n) for n>n0
0
 
LVL 7

Expert Comment

by:Xxavier
ID: 12180148
This is obviously homework.
0
 

Author Comment

by:jshantz4
ID: 12182074
Which is why I asked for ideas on how to tackle it -- *not* for someone to solve it for me.
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 7

Expert Comment

by:Xxavier
ID: 12182500
....which is what ozo has done, ie solve it.
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 12182511
Start with the definition of big-Oh equivalence.   f(x) is big-Oh equivalent to g(x) if-and-only-if the limit of f(x)/g(x) as x approaches +infinity is a nonzero constant.  

The standard notation for big-Oh, O(f(x)) = g(x), is kind of confusing because it makes the big-Oh look like a function when the whole concept of big-Oh really is to define equivalence classes for functions.
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 12182545
I think Ozo didn't solve it right, anyway.  I think he solved something for lower bounds (big-Omega?), not for big-Oh.  Big-oh is about asymptotic proportional equality, not <= comparisons.
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 12182758
Ok, sorry, I'm wrong.  According to Knuth vol 1 p. 107, big-Oh is defined as f(x)<=M*g(x) for all x > x0 for some M and x0 iff f(x) == O(g(x)).  So x^2 == O(x^3), but x^3 is not O(x^2).  Ozo had it right.
0
 

Author Comment

by:jshantz4
ID: 12231282
Xavier: Can I control what someone posts on my question?  Besides, I'd hardly call that a solution.  The solution -- which I eventually found on my own -- was several more lines long.  However, since no one else provided anything else, I'm going to have to accept it.
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
When we purchase storage, we typically are advertised storage of 500GB, 1TB, 2TB and so on. However, when you actually install it into your computer, your 500GB HDD will actually show up as 465GB. Why? It has to do with the way people and computers…
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
Suggested Courses

617 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question