Landau Notation: Why is O(f) (not) the set all g < c*f? I am somewhat confused here about the Landau notations. Let's say we are dealing with function from $\mathbb{N}$ to $\mathbb{R}$. Then we can define $\mathcal{O}(f) = \left\{ g : \mathbb{N} \to \mathbb{R} | \exists c &gt; 0 \text{ such that } g \leqslant cf\right\}$. Ok, so every function $g$ that is asymptotically smaller than $f$ is in this set. So if we have an algorithm $A$ that runs at most exactly $n^2+10$ steps, then
$g1 : \mathbb{N} \to \mathbb{R} \text{ with } n \mapsto n^2 \in \mathcal{O}(A)$.
But also
$g2 : \mathbb{N} \to \mathbb{R} \text{ with } n \mapsto n \in \mathcal{O}(A)$
or even
$g3 : \mathbb{N} \to \mathbb{R} \text{ with } n \mapsto 0 \in \mathcal{O}(A)$
satiesfy the condition to be elements of $\mathcal{O}(A)$. So, why would normally only $g1$ be the function of which one would say $g1 = \mathcal{O}(A)$ ?
I understand the $=$-sign is formally incorrect and just a convention, but if $g2$ and $g3$ also are in $\mathcal{O}(A)$ why define $\mathcal{O}$ this way, if $g1$ is the only function we care about to describe the asymptotic complexity of $A$?
Edit
So, I see I had misunderstood the idea a little. So far I thought $\mathcal{O}$ would take an algorithm and return how long it runs asymptotically. So, what $\mathcal{O}$ actually does is the following&gt;:
If we have an algorithm $A$ saying that
$$\forall c &gt; 0. \forall x \in domain(A).\lim_{n\to\infty} T(A(x)) \leqslant cn$$ would be the same as $$T(A) \in \mathcal{O}(n)$$
Is that correct?? Something looks still wrong about that.
($T$ being the function that returns the number of steps the computation required.)
There are at least three fundamental misunderstandings, here.


$O(\cdot)$ only makes statements about large enough inputs to the function. It's not that there exists some&nbsp;$c$ such that $g\leq c\,f$ for all&nbsp;$n$, but just for all large enough&nbsp;$n$.
The argument of $O(\cdot)$ is a (mathematical) function. If $A$&nbsp;is an algorithm, it makes no sense to write $O(A)$: it doesn't type-check. In particular, for an algorithm&nbsp;$A$, we don't talk about "the order of&nbsp;$A$". Rather, $O(\cdot)$ is a way of comparing mathematical functions: $O(f)$&nbsp;is the set of all mathematical functions&nbsp;$g$ such that $g(n)\leq c\,f(n)$ for some&nbsp;$c$ and all large enough&nbsp;$n$.
$O(f)$ is the set of all mathematical functions&nbsp;$g$ such that $g(n)\leq c\,f(n)$ for some&nbsp;$c$ and all large enough&nbsp;$n$. So it's simply not true that, in your example, $g_1$ would be the only function you'd describe as being $O(n^2+10)$.


$O(\cdot)$ is defined that way because it's useful to do so: it's a way of comparing functions and it doesn't care what you use those functions for. ($O(\cdot)$ doesn't care about complexity theory, just as the meter doesn't care about Mount Everest.) So, when we say that the running time of an algorithm is, say, $O(n^2)$, we just mean that, for large enough inputs, it's no worse than some constant times&nbsp;$n^2$. Often, we say it that way because we don't know anything more precise.  In the same vein, I'm pretty sure that you have less than a million dollars in the bank but It would be hard for me to find out how much less.

In cases where we do know something more precise, we might use $\Theta(\cdot)$, or we might use separate $O(\cdot)$ and $\Omega(\cdot)$ bounds.  For example, we might say that the running time of some algorithm is $\Theta(n\log n)$, meaning that there are constants $c_1$ and&nbsp;$c_2$ such that, for all large enough&nbsp;$n$, the running time is between $c_1n\log n$ and $c_2n\log n$.  For some other algorithm, we might only be able to prove that its running time is $O(n^3)$ and $\Omega(n^2)$, meaning that there are constants $c_1$ and $c_2$ such that, for large enough&nbsp;$n$, the running time is between $c_2n^2$ and $c_1n^3$.