Big-O Notation Advice

Which of these functions is not O(n²)?

A. O(n²log₂n)

B. O(log₂(log₂n)

C. O(nlog₂n)

D. (log₂ⁿ)²

I believe, that it is not A, because n² takes dominance in that one, which would make it a O(n²) as well.

My question becomes how do you figure out which one is not a O(n²)? I have not worked much with logarithms, and I am still fuzzy about how to work with them.

Thanks.

Solution

Answer is A

Big-O is an upper bound and in programming represents the worst-case runtime. For example f(n) = n^2 means f(n) is O(n^2) and O(n^3) and O(n^100*logn). So O(n^2) is also O(n^3) but O(n^3) is not O(n^2)

In the case of your question, the only answer that is > n^2 is A. Graphing the functions can help you visualize it. As you can see A (red) is the only one increasing faster than n^2 (black)

This article may help you as well https://en.wikipedia.org/wiki/Big_O_notation and go to Orders of common functions