03/08/2011, 04:09 PM
(03/08/2011, 07:37 AM)dyitto Wrote: I've been reading this explanation.
Now take functions
f(x) = x^x
g(x) = (x + 1)^(x + 1)
According to the definition of "little-oh", I'd conclude that f(x) = o(g(x)).
Am I right?
Yes, because f is not \( \Omega(g) \): if you would chose any constant C>0 (> 0 is essential though omitted in that text, better look at wikipedia), then you always find
x^x < C (x+1)^(x+1) for large enough x
because
x^x / (x+1)^(x+1) < (x+1)^x / (x+1)^(x+1) = 1/(x+1) < C