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

Question

f(n)=(log(n))^log(n)

g(n)= n/log(n)

f = O(g(n))?

Answer 1

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.

Answer 2

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.