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.
精彩评论