Which of these function has a higher increasing for infinity?

Question

I would like to compare two given functions for their asymptotic increasing, to see which of them has a higher increasing.

Given functions f(n) = n*ln(n) and g(n)= $e^log_2(n)$, my solution is given in the picture below:

The result is, that n*ln(n) is faster. By looking at the graph, I don't believe that. Can anyone tell me how to solve that?

Answer 1

Your graph is telling the truth, g(n) grows faster than f(n). Here is why:

The key equation is the following

log_a(x) = log_b(x)/log_b(a)                         (*)

which is easily proven by definition since

b^{log_a(x)log_b(a)} = (b^{log_b(a)})^{log_a(x)}     ; t^{sr} = (t^s)^r
                     = a^{log_a(x)}                  ; b^{log_b(a)}=a
                     = x.

(the proof is complete, but you can take log_b on both sides to convince yourself further)

Now we can use (*) for our particular case:

log_2(n) = log_e(n)/log_e(2)                         (**)

and get

g(n) = e^{log_2(n)}                                  ; def of g(n)
     = e^{log_e(n)/log_e(2)}                         ; (**)
     = (e^{log_e(n)})^{1/log_e(2)}                   ; t^{s/r} = {t^s}^{1/r}
     = n^{1/log_e(2)}                                ; e^{log_e(n)}=n
     = n^{log_2(e)}                                  ; (*) for x=b=e, a=2

But since e > 2, we deduce that log_2(e) > 1, say, log_2(e) = 1 + δ, with δ > 0. Thus

g(n) = n*n^δ

We have now to compare g(n) with

f(n) = n*ln(n)                                       ; def of f(n)

which is the same as comparing n^δ with ln(n). For this we can compute

lim n^δ/ln(n)

which is the same as

lim x^δ/ln x                                         ; x → ∞

where we can use L'Hôpital's rule

lim δx^{δ-1}/x^{-1} = lim δ x = δ lim x = ∞          ; δ > 0. 

Hence

lim g(n)/f(n) = ∞

and g(n) grows faster than f(n).