Why the time complexity O ( N*Log( N ) ) is considered polynomial time?
In: Mathematics
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.
Latest Answers