?
Solved

Big-Oh Proof

Posted on 2004-09-28
8
Medium Priority
?
1,429 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
  • 3
  • 2
  • 2
  • +1
8 Comments
 
LVL 85

Accepted Solution

by:
ozo earned 1500 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
What Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

 
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 Kind of Coding Program is Right for You?

There are many ways to learn to code these days. From coding bootcamps like Flatiron School to online courses to totally free beginner resources. The best way to learn to code depends on many factors, but the most important one is you. See what course is best for you.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Aerodynamic noise is the cause of the majority of the noise produced by helicopters. The inordinate amount of noise helicopters produce is a major problem in the both a military and civilian setting. To remedy this problem the use of an aerogel coat…
With the functions here, you can parse, convert, and format back and forth between feet and inches and fractions and decimal inches - for normal as well as extreme values and with extreme precision.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

568 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