Thus (n log n) is "bigger" than ((log n)3). This could be easily generalized to ((log n)k) via induction.
Algorithm complexity, log^k n vs n log n
-
30-07-2022 - |
Pergunta
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.
Solução
Outras dicas
If you graph the two functions together you can see that n log(n) grows faster than log3 n.
To prove this, you need to prove that n log n > log3 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 logx n for positive x.