Search code examples
algorithmasymptotic-complexity

Which grows faster 2^(2^n) or n^(2n)

I am quite sure that the former function grows faster. But when I plotted it on Wolfram alpha, the latter seemed to dominate.

In general, if I want to compare f(n) and g(n), can an analysis of log(f(n)) and log(g(n)) be used for analysis of the original functions ?

Solution

  • log(x) is an increasing function, hence f(x) <= g(x) if and only if log(f(x)) <= log(g(x)).

    In this case,

    log(2^2^n) = 2^n*log(2)

    This is growing exponentially

    But

    log(n^(2*n)) = 2*n*(log(n)) = O(nlog(n))

    which is sub-exponential.

    Thus, you are correct that 2^2^n asymptotically dominates n^(2*n).

    I'm not sure what you were doing with Wolfram Alpha. The fact that 2^2^n dominates n^(2*n) shows up even for single digit n: 2^(2^9) is approximately 1.34 x 10^154 but 9^(2*9) is only 1.5 x 10^17.