Which function is greater as n -> oo? n^(1.01) or n(log n)^2?

Question

I've tried solving this using limits and L'Hopital's rule but I'm not convinced my answer is correct. Intuitively I want to say n^(1.01) is eventually greater than n (log n)^2, but a preliminary check on the graphing calculator shows n (log n)^2 even with a viewing window from 0 to 1e99 in both x and y. My limit approach told me n^(1.01) is greater, but I'd like to know what others think.

So, that first answer was completely useless. I already said I tried limits and L'Hopital's rule. I just want someone to double check my work. The limit does go to infinity as I calculated it, but this is for an algorithms class and it's been ages since I've had calculus, so I'm not at all confident in the veracity of my answer. If I were just trying to get an easy answer I wouldn't have already gone to all this trouble.

Answer 1

You've been getting a lot of bad answers to this one. If you look at the limit of the ratio of n^a and log n as n goes to infinity, you find, using L'Hopital's rule, that
lim n^a /log n=
lim an^(a-1) /(1/n)
=lim an^a =infinity

In other words, any positive power of n, no matter how small will go to infinity faster than log n. For your question,
n^(1.01) /[n (log n)^2]=[n^(.005) /log n]^2
goes to infinity, so n^1.01 goes to infinity faster than n (log n)^2.

To get an idea of how long it takes for n^1.01 to overtake n (log n)^2, we need to find out when n^.005 overtakes log n. If we write n as e^x, then we are asking when e^[.005x] becomes larger than x. Clearly, this is not the case for x=1000 but is true for x=1500.

Translating back into n's, we see that n^1.01 is smaller than n (log n)^2 when n=e^1000, which is about 1.9 EE 434, but larger when n=e^1500, which is about 2.7 EE 651.

Addendum: the actual intersection point happens when x is about 1456, so n is about e^1456, which is about 2 EE 632. This is clearly well beyonf 1EE99.

Addendum: I just realized, you probably wanted log base 10 rather than log base e. The answer is still the same: n^1.01 goes up faster than n (log n)^2. In this case, if we write n=10^x, we want to know when 10^.005x is more than x. This is true for some small values of x (x<1) which correspond to n<10. In order to overcome it again, we need x to be larger than about 548, so n needs to be more than 1EE 548.

Answer 2

too complex to write
second one is faster, here's why

n^1.01 = n * n^(1/100)

so n^1.01 / nlog(n)^n = n^1/100 / log(n)^2

that is oo/oo, so you can use l'hopital

now you have:

(n^1/100)' = 1/100 * n^(1/100-1) = 1/100 * n^(-99/100) =
= 1/100 * 1 / (n^100/99) = (1/100 ) / (n*n^1/99) =

second one is as hard to write:

(log(n)^2)' = 2* [ ln(n) / ( ln(10)^2 * n)] = ln(n^2) / (n*ln(10)^2)

now put that in fraction and you are left with a limes of a function that goes to zero... therefore nlog(n)^2 is bigger

Answer 3

n(logn)^2 is greater than n^1.01 for n > 10