# Big-O notation Basics, is it related to derivatives?

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)

-
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

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.

-
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

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)$.

-
I would up vote if I could. – Jeff Oct 26 '12 at 20:05
@Jeff: I bet you can :) – Hagen von Eitzen Oct 26 '12 at 20:10

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

-
Thank you for the reference. I found a PDF and will browse through this. – Jeff Oct 26 '12 at 19:42

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))$

-