If g(n) = sqrt(n)^sqrt(n), does the complexity of g(n) = O(2^n)?

Question

If g(n) = sqrt(n)^sqrt(n), does the complexity of g(n) = O(2ⁿ)?

Any help is appreciated.

Answer 1

A useful technique when comparing two exponential functions is to get them to have the same base:

√n^√n = (2^{lg √n})^√n = 2^{√n lg √n}

Now you're comparing 2^{√n lg √n} against 2ⁿ, and hopefully from that it's easy to see that the former function does not grow as rapidly as the latter, so √n^√n = O(2ⁿ) is indeed true.