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

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 an, 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.
    • 链接地址: http://www.djcxy.com/p/52492.html

    上一篇: Node.js + Nginx

    下一篇: f（n）= n ^ log（n）复杂多项式或指数