The big O notation

Question

I am reading about Big O notation. In the book I have, there is an example in which the complexity of n² is in class of O(n³). That doesn't seem logical to me because n³ depends on n and it isn't just a plain constant multiplier that we can "get rid of."

Please explain to me why those two are of the same complexity. I can't find an answer on this forum or any other.

Answer 1

Big O determines an upper bound for large values of n. O(n³) is larger than O(n²) and so an n² program is still O(n³). It's also O(n⁴), O(*n⁵), ..., O(n^infinity).

The reverse is not true, however. An n^3 program is not O(n²). Rather it would be Omega(n²), as Omega determines a lower bound (how much work we have to do at least).

Big O says nothing of this upper bound being "tight", it just needs to be higher than the actual complexity. So while an n*n complexity program is bounded by O(n³), that's not a very tight bound. O(n²) is tighter and more informative.