1
$\begingroup$

In CLRS the author said

"Technically, it is an abuse to say that the running time of insertion sort is $O(n^2)$, since for a given $n$, the actual running time varies, depending on the particular input of size $n$. When we say “the running time is $O(n^2)$,” we mean that there is a function $f(n)$ that is $O(n^2)$ such that for any value of $n$, no matter what particular input of size $n$ is chosen, the running time on that input is bounded from above by the value $f(n)$. Equivalently, we mean that the worst-case running time is $O(n^2)$. "

What I have difficulties understanding is why did the author talked about an arbitrary function $f(n)$ instead of directly $n^2$.

I mean why didn't the author wrote

"When we say “the running time is $O(n^2)$,” we mean that for any value of $n$, no matter what particular input of size $n$ is chosen, the running time on that input is bounded from above by the value $cn^2$ for some +ve $c$ and sufficiently large n. Equivalently, we mean that the worst-case running time is $O(n^2)$".

I have very limited understanding of this subject so please forgive me if my question is too basic.

$\endgroup$
4
  • $\begingroup$ "is bounded from above by the value $cn^2$ for some $+$ve $c$" is not exactly what $O(n^2)$ says. For example, $cn^2$ is always $0$ for $n=0$ and $0$ might not be a bound for the running time, for an input of that size. You need to add $n>n_0$, for some $n_0$. $\endgroup$ – plop Aug 23 '20 at 14:54
  • $\begingroup$ Regarding $f$, the function is not arbitrary. There are conditions for it, which are mentioned. I think what you mean is why did they name a function that constitutes a bound for the running time for all inputs of a given size. That was just style. With some fixes, your wording can also say the same while not giving the bound any name. $\endgroup$ – plop Aug 23 '20 at 14:57
  • $\begingroup$ I edited the question to mention the condition of $n \ge n_0$. Is my and the author's statement identical now? $\endgroup$ – rsonx Aug 23 '20 at 15:03
  • $\begingroup$ Note CLRS has four authors. $\endgroup$ – Yuval Filmus Aug 23 '20 at 15:04
2
$\begingroup$

I think that the point that the authors are trying to make is the following:

The exact running time depends on the input.

When we say that the running time of insertion sort is $O(n^2)$, what we really mean is:

The worst-case running time of insertion sort is $O(n^2)$.

Actually, we could be even more verbose, and mention that by worst-case we mean worst case with respect to the length of the array:

The worst-case running time of insertion sort, in terms of the length $n$ of the input, is some function $f(n)$ which belongs to the class $O(n^2)$.

This is equivalent to the following claim:

There exists $C$ such that insertion sort takes time at most $Cn^2$ when running on an input of length $n$.

Note that there is no need to specify a lower bound on $n$ – if the running time is bounded by $C_1n^2$ for all $n \geq N$, then it is bounded by $C_2n^2$ for all $n \geq 1$. You can take $C_2$ to be the maximum between $C_1$ and the worst-case running times on inputs of length at most $N$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.