Menu
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.
307
Yes, O(nlogn) is polynomial time. From http://mathworld.wolfram.com/PolynomialTime.html, An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is O(n^m) for some nonnegative integer m, where n is the complexity of the input.
Any algorithm whose time complexity function cannot be so bounded is called an exponential time algorithm (although it should be noted that this definition includes certain non-polynomial time complexity functions, like nlogn, which are not normally regarded as exponential functions).
It has a guaranteed running time complexity of O ( n l o g ( n ) ) O(n \ log (n)) O(n log(n)) in the best, average, and worst case. It essentially follows two steps: Divide the unsorted list into sub-lists until there are N sub-lists with one element in each ( N is the number of elements in the unsorted list).
Examples of O(N log N) algorithms: Merge sort, Heap sort, and Quick sort.
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
130
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
