(log(n))^log(n) and n/log(n), which is faster?

f开发者_如何学运维(n)=(log(n))^log(n)

g(n)= n/log(n)

f = O(g(n))?

Take the log of both sides:

log(f(n)) = log(log n) * log n

log(g(n)) = log(n) - log(log(n)) = log(n)(1 - log(log(n))/log(n))

Clearly log(log(n)) dominates (1 - log(log(n))/log(n)), so g is O(f). f is not O(g). Since it's homework, you may need to fill in the details.

It's also fairly easily to get an idea what the answer should be just by trying it with a large number. 1024 is 2^10, so taking n=1024:

f(n) = 10^10

g(n) = 1024/10.

Obviously that's not a proof, but I think we can see who's winning this race.

f(n) grows faster than g(n) if and only if f(eⁿ) also grows faster than g(eⁿ) since exp is strictly increasing to infinity (prove it yourself).

Now f(eⁿ) = nⁿ and g(eⁿ) = eⁿ / n, and you can quote the known results.

If Limit[f[x] / g[x], x -> Infinity] = Infinity, then f[x] grows faster than g[x].

Limit[Log[x] ^ Log[x] / (x / Log[x]), x -> Infinity] = + Infinity

So, Log[x] ^ Log[x] grows faster than x / Log[x]

Mathematica gives the limit of f(n) / g(n) as n tends towards infinity as infinity, which means that f grows faster. This means that g(n) belongs to (=) O(f(n)).

You can use this for example if you don't have Mathematica.

f is vastly bigger. By n^loglog(n) -1 . log n