The running time of algorithm is at most $O(n^2)$

Question

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.

• Bernhard Barker: I'd say the problem with using "at most O(n^2)" is that there isn't a particularly well-known and well-defined meaning of "at most" in this context, which can lead to ambiguity (unless the surrounding context makes the meaning clear). I can think of a few possible things that one might want to imply with that.
• Inertial Ignorance: Technically it could be stated as "in the worst case, the running time of the algorithm is O(n^2) and higher".

Answer 1

The two phrases

The running time is $O(n^2)$

and

The running time is at most $O(n^2)$

mean the same thing.

This is similar to the following two equivalent claims:

• $x = y$ for some $y \leq z$.
• $x \leq y$ for some $y \leq z$.

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)$".

• Bernhard Barker: "the first part runs in O(n), which is at most O(n^2)" - I wouldn't use "at most" there, but rather just "also" or say just it's O(n^2). "At most" used in that way would to me imply that you can't say it's O(n^3), but of course you can say that.
• Yuval Filmus: You wouldn’t, some would. It’s a matter of style.
• Fraser Orr: I don't agree with this at all. To use a trivial example of Quicksort, you will often hear its running time described as O(n.log(n)), and that is indeed the average running time, but its worst case is O(n²), so it is not at all true to say that "the running time is O(n²)" is the same as saying the running time is at most O(n²)". What a person means by "running time" is contextual. I'd say it usually means average running time not worst case running time.
• Discrete lizard: @FraserOrr As far as I'm aware, there are two different meanings in use for "running time" without specification. One is "the metric we care about in the situation where we apply it", which you mention here. The other is "the bound holds in any (worst, best, average, etc.) case", which means it is the worst case running time. I don't think "at most" helps much to disambiguate these two usages. I think it's better to be fully explicit and write "X case running time" if you don't want to be ambiguous.
• Fraser Orr: @Discretelizard for sure it would be better to be explicit, but I would say that if someone said that the running time was at most O(n²) it is fairly unambiguous, if not idiomatic, that they mean the worst case runtime.

Answer 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)$.

• Cort Ammon: This points out the other phrasing you will see, "The runtime is on average $O(n^2)$"

Answer 3

My reading is that it's not necessarily a tight bound, ie. we know the algorithm is $O(n^2)$, but we don't know if it's (for example) $O(n^{1.99})$

• usul: I wouldn't assume this is the right interpretation without more context, but it's definitely possible.

Answer 4

"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.

• Fax: +1. I would also interpret it as "I've proven it to be $O(n^2)$ but I haven't checked if it could be e.g. $O(n \log n)$".

Answer 5

You can just view $\mathcal{O}(n^2)$ as an anonymous function drawn from the underlying class.

The statement means: The running time of the algorithm is at most quadratic in the input length $n$.

I do not think there is anything controversial or wrong here.

Answer 6

I understand it so, that, perhaps, saying "$f$ is at most $O(n^2)$", the speaker wants to emphasize, exaggerate his attitude to upper bound $O(n^2)$ as least one.

Good point anyway.

Answer 7

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.