CODEWITHSUNDEEP
big-o
Yahiko Kikikoto
Yahiko Kikikoto

Reputation: 748

Is O(n Log n) in polynomial time?

Is O(n Log n) in polynomial time? If so, could you explain why?

I am interested in a mathematical proof, but I would be grateful for any strong intuition as well.

Thanks!

Upvotes: 25

Views: 31617

Answers (4)

Syd Kerckhove
Syd Kerckhove

Reputation: 833

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.

From http://en.wikipedia.org/wiki/Big_O_notation,

f is O(g) iff

$ \hspace{1px} \exists k > 0 \hspace{3px} \exists n_0 \hspace{3px} \forall n > n_0: \hspace{3px} | f(n) | \leq | g(n) \cdot k | \hspace{1px}$

I will now prove that n log n is O(n^m) for some m which means that n log n is polynomial time.

Indeed, take m=2. (this means I will prove that n log n is O(n^2))

For the proof, take k=2. (This could be smaller, but it doesn't have to.) There exists an n_0 such that for all larger n the following holds.

n_0 * f(n) <= g(n) * k

Take n_0 = 1 (this is sufficient) It is now easy to see that

n log n <= 2n*n

log n <= 2n

n > 0 (assumption)

Click here if you're not sure about this.

This proof could be a lot nicer in latex math mode, but I don't think stackoverflow supports that.

Upvotes: 22

user1654183
user1654183

Reputation: 4605

Yes. What's the limit of nlogn as n goes to infinity? Intuitively, for large n, n >> logn and you can consider the product dominated by n and so nlogn ~ n, which is clearly polynomial time. A more rigorous proof is by using the the Sandwich theorem which Inspired did:

n^1 < nlogn < n^2.

Hence nlogn is bounded above (and below) by a sequence which is polynomial time.

Upvotes: -1

Dylan Meeus
Dylan Meeus

Reputation: 5802

It is, because it is upper-bounded by a polynomial (n). You could take a look at the graphs and go from there, but I can't formulate a mathematical proof other than that :P

EDIT: From the wikipedia page, "An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm".

Upvotes: 5

nullptr
nullptr

Reputation: 11058

It is at least not worse than polynomial time. And still not better: n < n log n < n*n.

Upvotes: 4

Related Questions