Meaning of 'running time is $O(n^2)$'

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.

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

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

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

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