Why the time complexity O ( N*Log( N ) ) is considered polynomial time?
In: Mathematics
In short: polynomial time complexity is any complexity function that can be bound by a polynomial function. log(N) < N (for large values of N), so N*log(N) can be bound by the polynomial function N^(2), making it polynomial time.
Big O notation is about bounding the growth of functions. f(n) = O(x(n)) means that there there exist a pair of constant k1 and k2 such that x(n) * k1 <= f(n) <= x(n) * k2 for all n above some constant c. As a generally convention, x(n) is a exponential function, with linear time being x(n) = n and polynomial time being x(n) = n^2. Since log(n) can be bounded as O(n), it is trivial to show that n log(n) is O(n^2).
Now, I’d argue that that since there are lots of functions that are O(n log (n)), that is should be one of the conventional used complexity classes, but that is not the convention.
[removed]
Latest Answers