Big-Oh Proof

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?
jshantz4Asked:
Who is Participating?

[Webinar] Streamline your web hosting managementRegister Today

x
 
ozoConnect With a Mentor Commented:
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
 
XxavierCommented:
This is obviously homework.
0
 
jshantz4Author Commented:
Which is why I asked for ideas on how to tackle it -- *not* for someone to solve it for me.
0
Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
XxavierCommented:
....which is what ozo has done, ie solve it.
0
 
NovaDenizenCommented:
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
 
NovaDenizenCommented:
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
 
NovaDenizenCommented:
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
 
jshantz4Author Commented:
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
All Courses

From novice to tech pro — start learning today.