f(n)=n^log(n) complexity polynomial or exponential

I'm trying to figure out whether f(n)=n^(logb(n)) is in Theta(n^k) and therefore grows polynomial or in Theta(k^n) and therefore grows exponentially.

First I tried to simplify the function: f(n) = n^(logb(n)) = n^(log(n)/log(b)) = n^((1/log(b))*log(n)) and because 1/log(b) is constan开发者_运维百科t we get f(n)=n^log(n).

But now I'm stuck. My guess is that f(n) grows exponentially in Theta(n^log(n)) or even hyper exponentially because the exponent log(n) is also growing.

You can write n^(log(n)) as (k^(logk(n)))^(log(n)) = k^(K*(log(n)^2)). Since (log(n))^2 < n for n large enough, then this means that n^(log(n)) will grow slower than k^n

Try substituting n with b^m, which makes logb(n) = m. That should get you an idea of where to go.

it seems like it's not theta(exponential) or theta(polynomial); the posters above showed why it is not exponential. The reason why it is not polynomial can be done with a simple proof by counter example.

proof that n^logn is not O(n^k):

• suppose there is some k, with some c and n_0 such that for n>n_0, c*n^k > n^log n. this is the definition of O(n^k).
• it is simple to find a n, with the constants, such that this doesn't hold.
• if c>1, then that n is (ck)^ck.
• if c<1, then that n is k^k.