Big O of n^1.001 vs n*log n / log 2?

Question

This question is throwing me for a loop, and I hope StackOverflow is the right place to ask this. The question asks

n^1.001 = O(n log n) (log is base 2)

in other words, does n log n grow faster than n^1.001.

I keep going around in circles on this one. I graphed n^1.001 vs log n (I took out n since n is on both sides of the equation). I graphed them up to about 10^32 or so before my program crashed, and even up to there, n^0.001 had not even reached 2, whereas log n was much larger. However, I wonder, and haven't been able to prove either way, that eventually, n^1.001 will pick up and start growing a lot faster than n log n, since it has an exponent larger than 1.

Is this correct? Which has a larger growth function?

Answer 1

Think about the fact that:

n^(1/2) > log(n) for n > 10,
n^(1/4) > log(n) for n > 100,
n^(1/8) > log(n) for n > 10000, etc.

It's easy to extrapolate that n^ε > log(n) for all ε > 0, n sufficiently large. Hope that Helps!