Solved

Big-Oh Proof

Posted on 2004-09-28
8
1,412 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 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
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!

 
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

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Functions 7 83
Homework Math Question 1 124
110V Lasko bladeless fan blows with a burning smell 5 94
Auto Adjust Percent rate 5 62
Complex Numbers are funny things.  Many people have a basic understanding of them, some a more advanced.  The confusion usually arises when that pesky i (or j for Electrical Engineers) appears and understanding the meaning of a square root of a nega…
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…
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.
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…

713 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