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$

2 Answers 2

3
$\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$
    – user127304
    Oct 31, 2020 at 11:34
  • $\begingroup$ No. It is any function which is $O(n^2)$. For example, it could be $2n^2$. $\endgroup$ Oct 31, 2020 at 11:35
  • $\begingroup$ got it now. thank you very much. $\endgroup$
    – user127304
    Oct 31, 2020 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$
    – user127304
    Oct 31, 2020 at 10:02
  • $\begingroup$ Yes, in your case $f(n)=n^2$. $\endgroup$
    – zkutch
    Oct 31, 2020 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.