Algorithm complexity, log^k n vs n log n

Question

I am developing some algorithm with takes up O(log^3 n). (NOTE: Take O as Big Theta, though Big O would be fine too)

I am unsure whereas O(log^3 n), or even O(log^2 n), is considered to be more/less/equaly complex as O(n log n).

If I were to follow the rules stright away, I'd say O(n log n) is the more complex one, but still, I don't have any clue as why or how.

I've done some research but I haven't been able to find an answer to this question.

Thank you very much.

Answer 1

Thus (n log n) is "bigger" than ((log n)³). This could be easily generalized to ((log n)^k) via induction.

Answer 2

If you graph the two functions together you can see that n log(n) grows faster than log³ n.

To prove this, you need to prove that n log n > log³ n for all values of n greater than some arbitrary number c. Find such a c and you have your proof.

In fact, n log(n) grows faster than any log^x n for positive x.