How is the time complexity of the following function O(n³)?

Question

I was going through the Algorithm lecture series of Stanford University on Coursera by Tim Roughgarden. There, he gave a multiple choice question to find the running time complexity of a function, which is given below in the image.

In this question, the last three options are correct. I understand how the first two options for Ω (Omega) and Θ (Theta) are correct just by looking at the function, but I am unable to grasp how the last option is correct because as far as I can tell, the running time complexity should be O(n²) instead of O(n³).

Can anyone please explain where I am wrong?

Answer 1

To be mathematically precise, big O, big Omega, etc are all sets, not functions. So, when we say T(n) = O(n^3), we really mean that T(n) is in the set O(n^3). But since it is not easy to typeset the "in the set" notation, we usually just end up writing that T(n) = O(n^3). Hence, it cause a bit of confusion, but basically O(n^3) is simply the set of functions that do not grow faster than n^3. And of course, the given T(n) does not grow faster than n^3, so T(n) is in the set O(n^3).

And similarly, T(n) is in the sets O(n^4), O(n^5), O(n^3 log n), O(n^127), O(n^n^n), etc.

So, if you had a fifth option in the question: T(n) = O(n^2), that would be true as well.