The problem is that if an algorithm is $O(n^2)$ then it is also $O(n^3)$ and $O(n^4), O(n^n), \ldots$ and the phrase 'at most' does not make sense in this situation.
For this reason, I am not sure whether this statement is correct or not.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
The two phrases
The running time is $O(n^2)$
The running time is at most $O(n^2)$
mean the same thing.
This is similar to the following two equivalent claims:
Why would we ever use "at most $O(n^2)$", then? Sometimes we want to stress that the bound $O(n^2)$ is loose, and then it makes sense to use "at most $O(n^2)$". For example, suppose that we have a multi-part algorithm, which we want to show runs in time $O(n^2)$. Suppose that we can bound the running time of the first step by $O(n)$. We could say "the first part runs in $O(n)$, which is at most $O(n^2)$".
“At most” might mean “at worst” i.e. that the worst-case time complexity is $O(n^2)$.
For example one might say that “Quicksort is at most $O(n^2)$,” meaning that no matter what infinite subset of the inputs you look at, the complexity on that subset is never more than $O(n^2)$.
"f(n) is in O(n^2)" means f(n) ≤ cn^2 for all large n and for some c > 0. Clearly if f(n) ≤ cn^2, then f(n) ≤ cn^3, cn^4 etc. So factually, "f(n) is in O(n^4)" is equally true. It just gives you much less information, so it may be less useful.
If someone says "f(n) is at most O(n^2)", I would interpret that as "I proved it is in O(n^2), but I couldn't be bothered to check whether it is possibly in a more narrow class". For example, if your algorithm does Step 1 which takes O(n^3) and then Step 2, and you can prove that Step 2 is in O(n^2), that's good enough for all purposes, and you wouldn't bother checking if it's maybe in O (n^2 / log n) or in O (n^1.5).
There's the class $\Theta(n^2)$ which means $c_1 n^2 ≤ f(n) ≤ c_2 n^2$ for all large n and for some $0 < c_1 < c_2$. Here you can't just substitute n^4 for n^2. And there is "asymptotic O(n^2)" which means f(n) is in O(n^2) and not in o(n^2), which means $c_1 n^2 ≤ f(n) ≤ c_2 n^2$ for infinitely many large n and for some $0 < c_1 < c_2$. Again, here you can't just substitue n^4.
First, just because it's O(n^2) doesn't mean it's O(n^3) or higher.
And sometimes "at most" is quite relevant. Consider, for example, Quicksort. In the real world it normally runs in very close to O(n log n) time, but for any given implementation you can devise an evil data set that makes it run in O(n^2) time. Certain naive implementations have a big problem with this as the evil data is simply already sorted data--add a few items and resort and it goes slow.
I am sure there are other algorithms that are like this but none come to mind right now.