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

Question

If g (n) = sqrt (n) ^{sqrt (n)} does the complexity g (n) = O (2 ⁿ ) hold?

Any help is appreciated.

Answer 1

A useful method when comparing two exponential functions is to make them have the same base:

& radic; n ^{& radic; n} = (2 ^{lg? radic; n} ) ^{? radic; n} = 2 ^{? n lg & Radic; P}

Now you are comparing 2 ^{& radic; n lg & radic; n} versus 2 ⁿ and I hope it’s easy to see from this that the former function does not grow as fast as the latter, so n ^{& radic; n} = O (2 ⁿ ) is really true.

Answer 2

Other proofs are short and pleasant, but here is a more detailed proof in order to proceed to the definitions of large designations and the calculation of the necessary limits.

The function g(n) bounded at the top by another function f(n) with a large O ( g(n) = O(f(n)) ), if it contains ( source )

Insert functions and we need to calculate

First, a little algebraic massage on the term g(n) . By root identities, it contains sqrt(n) = n^(1/2) . In addition, it has the value (x^a)^b = x^(a*b) . Wherein:

In addition, 2^n is exp(log( 2^n )) by logarithmic identities, and then log(a^b) = b*log(a) we have 2^n = exp(log( 2^n )) = exp(n * log(2)) . The same can be applied to n^(1/2 sqrt(n)) , it becomes exp(log( n^(1/2 sqrt(n)) = exp(1/2*sqrt(n)*log(n)) . So now we have

At this point, we can compare the growth of indicators, i.e. compare

This limit is 0 because const * n grows faster than sqrt(n)*log(n) . This, in turn, can be shown that the calculation of the limit is explicit. Put 1/2 and log2 in the counter. Since n = sqrt(n) * sqrt(n) , we can simplify it:

This limit is indeed zero, because squareroot is growing faster than the logarithm of Orders for common functions . Thus, the indicator of the lower function grows faster than the indicator of the upper function. Thus, g(n) = O(2^n) strictly proved by the first theorem.

Answer 3

You can take O(log n) < O(sqrt(n)) ( The order of common functions is wikipedia )

The conversion works as follows:

 sqrt(n)^sqrt(n) 2^n # a^b = e^(ln(a) * b) e^(ln(sqrt(n)) * sqrt(n)) e^(ln(2) * n) # if e^a < e^b, then a < b ln(sqrt(n)) * sqrt(n) ln(2) * n # / sqrt(n) ln(sqrt(n)) ln(2) * sqrt(n) # ln(a^b) = b * ln(a) 0.5 ln(n) ln(2) * sqrt(n) # ln(a) / ln(b) = log(a base b) 0.5 log(n base 2) sqrt(n) # base and constant factor don't matter log(n) sqrt(n) 

I skipped complexity classes for simplicity. The above should be read from bottom to top for proper proof.