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.
$\begingroup$
$\endgroup$
-
$\begingroup$ 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. $\endgroup$ – Bernhard Barker Nov 1 '20 at 21:55
-
$\begingroup$ Technically it could be stated as "in the worst case, the running time of the algorithm is O(n^2) and higher". $\endgroup$ – Inertial Ignorance Nov 2 '20 at 1:37
$\begingroup$
$\endgroup$
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)$".
answered Nov 1 '20 at 9:49
-
1$\begingroup$ "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. $\endgroup$ – Bernhard Barker Nov 1 '20 at 21:50
-
1$\begingroup$ You wouldn’t, some would. It’s a matter of style. $\endgroup$ – Yuval Filmus Nov 1 '20 at 22:02
-
1$\begingroup$ 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. $\endgroup$ – Fraser Orr Nov 2 '20 at 5:28
-
$\begingroup$ @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. $\endgroup$ – Discrete lizard♦ Nov 2 '20 at 13:51
-
$\begingroup$ @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. $\endgroup$ – Fraser Orr Nov 3 '20 at 19:33
$\begingroup$
$\endgroup$
“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)$.
-
1$\begingroup$ This points out the other phrasing you will see, "The runtime is on average $O(n^2)$" $\endgroup$ – Cort Ammon Nov 2 '20 at 1:26
$\begingroup$
$\endgroup$
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})$
answered Nov 1 '20 at 22:35
BlueRaja - Danny PflughoeftBlueRaja - Danny Pflughoeft
1,3531 gold badge9 silver badges14 bronze badges
-
$\begingroup$ I wouldn't assume this is the right interpretation without more context, but it's definitely possible. $\endgroup$ – usul Nov 2 '20 at 2:47
$\begingroup$
$\endgroup$
"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.
-
$\begingroup$ +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)$". $\endgroup$ – Fax Nov 2 '20 at 14:27
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
