Search code examples
algorithmfunctioncomplexity-theory

Algorithmic equivalence

I came across this problem while studying algorithms in Java, where I am asked

to chose what 4 in the power of n is equal to. Though I cant find a reference or a resource

to direct me towards the right solution.

The function 4 in the power of n is equal to

Solution

  • OK so f(n) = 4^n grows faster asymptotically speaking than all of these except n^n. Exponential functions with a constant base grow faster than logarithms or any polynomial (constant exponent) expression. 4^n grows more slowly than n^n and so 4^n = O(n^n) is true generally. Proving this is fairly trivial for the case n > 4.