Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Big-Oh Proof

Posted on 2004-09-28
8
Medium Priority
?
1,421 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 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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
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

Industry Leaders: 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!

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 …
We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
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…

688 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