Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am having the hardest time with Big-O notation (I am using this Rosen book for the class I am in).

On the surface, Big-O reminds me of derivatives, rate of change and what not; is this proper thinking? If $f(n)$ is $O(g(n))$, would the derivatives have any affect on this?

Essentially is there a good resource for learning Big-O for the first time?

If I missunderstand this forum and need a specific question, then:

Prove that if $f(n)\le g(n)$ for all $n$, then $f(n) + g(n)$ is $O(g(n))$. (I'd rather gain an understanding of how to do this than to have an answer to a problem).

EDIT:

My attempt at the answer to my specific question using l'Hopital:

lim(x→∞) f'(x)/(f'(x) + g'(x)) = lim(x→∞)⁡1/(g'(x) 
share|improve this question
1  
A cautionary example that may help in getting some intuition for Big-$O$ vs. derivatives. Consider a function that (smoothly) connects the points $$(0,0), (1,1), (3,1), (4,4), (7,4), (8,8), \dots, (2^k, 2^k), (2^{k+1}-1, 2^k), (2^{k+1}, 2^{k+1}) \dots.$$ In other words, the function stays flat for long periods, than jumps up to meet up with $y=x$ again. Such a function satisfies $f(x)=O(x)$, but the derivative of $f$ can be arbitrarily large (even though the derivative of $g(x)$ isn't). In other words, Big-$O$ notation only says something about AVERAGE growth, not growth at all places. –  Kevin Costello Oct 26 '12 at 19:48
add comment

4 Answers 4

up vote 1 down vote accepted

I found this question (and the first answer) helpful: Big-O Notation and Asymptotics

For example, f(n) is O(g(n)). Then, f(n) may diverge (increase without bound). However, (f(n))/(g(n)) does not, as g(n) is always greater than f(n) beyond some number N.

So, really, it has more to do with the limit of the ratio of two functions than derivatives.

share|improve this answer
    
This is helpful, thank you. I found this: cs.unm.edu/~saia/362-s08/lec/lec2-2x2.pdf and the l'hopital rule comes up a lot. –  Jeff Oct 26 '12 at 19:44
    
@Jeff L'Hôpital's rule is very one-sided. If $f'(n)/g'(n)$ converges, then it informs you of the original limit. However in many many cases, $f'(n)/g'(n)$ fails to converge, and this tells you nothing about the original limit. That's why comparing derivatives in this general setting is doomed to failure. –  Erick Wong Oct 27 '12 at 4:33
add comment

Big-Oh is is not completely determined by derivatives. For example $\sin(x^2)\in O(1)$ but the derivative $2x\cos(x^2)$ is unbounded.

The claim that $f(n)\le g(n)$ implies $f(n)\in O(g(n))$ is false: Consider $g(n)=n$, $f(n)=-n^2$. But if you replace the condition with $|f(n)|\le g(n)$ then the claim is easy: That is almost the definition of $f(n)\in O(g(n))$. And of course trivially $g(n)\in O(g(n))$. Then since Big-ohs are closed under addition, also $f(n)+g(n)\in O(g(n)$.

share|improve this answer
    
I would up vote if I could. –  Jeff Oct 26 '12 at 20:05
2  
@Jeff: I bet you can :) –  Hagen von Eitzen Oct 26 '12 at 20:10
add comment

Concrete Mathematics is a good place to start with asymptotics and related ideas, particularly if you are in computer science (which your tags suggest).

share|improve this answer
    
Thank you for the reference. I found a PDF and will browse through this. –  Jeff Oct 26 '12 at 19:42
add comment

One more easy way of looking at this type of problem is noticing that if $f(n) \leq g(n)$ then $$ f(n)+g(n) \leq g(n) +g(n)=2g(n)= O(g(n)) $$ In fact it is easy to show that this sum is $\Theta(g(n))$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.