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?

(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

: 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

Intuitively I would say that the above functions f and g have about the same growth rate, since f simply stays one step behind g.

A function with a REAL different growth rate would be:

h(x) = x^(x^x)

So if I wanted to look into the relative growth of hyperoperational functions, then these Bachmannâ€“Landau notation apparently wouldn't be of much use in this context.