3
$\begingroup$

I have a question from Introduction to Algorithms by CLRS,

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 values of $n$, no matter what particular input of size $n$ is chosen, the running time on the input is bounded from above by the value of $f(n)$.

What do the authors mean by saying there exists a function that is $O(n^2)$? Do they mean that this function is from the set $O(n^2)$? Is the last part which I highlighted correct? I think it must be "... from above by $O(n^2)$." I appreciate your answers.

$\endgroup$
4
$\begingroup$

We say that a function $f(n)$ is $O(n^2)$ if there exist constants $C,N>0$ such that $f(n) \leq Cn^2$ for all $n \geq N$. We usually denote "$f(n)$ is $O(n^2)$" by "$f(n) = O(n^2)$".

An algorithm has running time $O(n^2)$ if its worst-case running time is $O(n^2)$. That is, if we denote by $T(n)$ the maximum running time of the algorithm on inputs of length $n$, then the algorithm has running time $O(n^2)$ if $T(n) = O(n^2)$.

Equivalently (and this is the point of the CLRS formulation), an algorithm has running time $O(n^2)$ if there exists some function $f(n) = O(n^2)$ such that the running time of the algorithm on an input of length $n$ is always at most $f(n)$.

If we denote the running time of the algorithm on the input $x$ by $T(x)$, and the length of $x$ by $|x|$, then we can see the difference between these two equivalent definitions by writing them out formally.

The first definition is $$ \max_{|x| = n} T(x) = O(n^2), $$ where the left-hand side defines a function of $n$, which we denoted above by $T(n)$.

The second definition states that for some $f(n) = O(n^2)$, $$ T(x) \leq f(|x|). $$

If the second definition holds, then in particular $$ \max_{|x|=n} T(x) \leq f(n), $$ and so $$ \max_{|x|=n} T(x) = O(n^2), $$ which is the first definition.

If the first definition holds, then we can take $f(n) = \max_{|x|=n} T(x)$ to obtain a function satisfying the second definition: $$ T(x) \leq \max_{|y|=|x|} T(y) = f(|x|), $$ where the first definition guarantees that $f(n) = O(n^2)$.

$\endgroup$
3
  • $\begingroup$ Sir, I want to ask it again to verify myself; $f(n)$ is simply $n^2$ in the example at hand, right? $\endgroup$
    – Alparslan
    Oct 31 '20 at 11:34
  • $\begingroup$ No. It is any function which is $O(n^2)$. For example, it could be $2n^2$. $\endgroup$ Oct 31 '20 at 11:35
  • $\begingroup$ got it now. thank you very much. $\endgroup$
    – Alparslan
    Oct 31 '20 at 11:36
2
$\begingroup$

Having, for non negative case, formal definition $$O(f)=\{g: \exists C>0, \exists N \in \mathbb{N}, \forall n>N, g(n) \leqslant Cf(n)\}$$ then we of course are considering big-$O$ as set.

If some $g \in O(n^2)$, then words "the running time on the input is bounded from above by the $\text{value of f(n)}$" means, as it is in definition, existence some $N_g, C_g$ such that $g(n) \leqslant C_gn^2$ for $\forall n>N_g$.

$\endgroup$
2
  • $\begingroup$ In this case, we are considering n squared function as function f, right? $\endgroup$
    – Alparslan
    Oct 31 '20 at 10:02
  • $\begingroup$ Yes, in your case $f(n)=n^2$. $\endgroup$
    – zkutch
    Oct 31 '20 at 10:12

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.