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

Question

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 constant 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.

Solution 1

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

Solution 2

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

Solution 3

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.

Comments

[sleske]

+1 for actually explaining how far you got and where you are stuck

[drizzd]

Where you have used that logarithmic growth is slower than any polynomial, which includes sqrt(n).

[sleske]

@drizzd: Since when is sqrt(n) a polynomial?

[Himadri Choudhury]

@sleske. sqrt(n) is technically not a polynomial, but it is n^0.5, and for algorithm complexity anything O(n^k) is considered polynomial time. At least that's how I've seen it defined.

[blubb]

@sleske: always been: sqrt(n) = n^(1/2) and that is polynomial

[sleske]

@Simon, drizzd: Well, the common definition of a polynomial (at least in general mathematics) only allows natural numbers as exponents. But of course if you just need an upper bound, it does not make a difference to allow arbitrary real exponents, so I'm really just nitpicking :-).