Landau Notation: Why is O(f) (not) the set all g < c*f?

Question

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 > 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>: If we have an algorithm $A$ saying that

$$\forall c > 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.)

Answer 1

There are at least three fundamental misunderstandings, here.

1. $O(\cdot)$ only makes statements about large enough inputs to the function. It's not that there exists some $c$ such that $g\leq c\,f$ for all $n$, but just for all large enough $n$.

2. The argument of $O(\cdot)$ is a (mathematical) function. If $A$ is an algorithm, it makes no sense to write $O(A)$: it doesn't type-check. In particular, for an algorithm $A$, we don't talk about "the order of $A$". Rather, $O(\cdot)$ is a way of comparing mathematical functions: $O(f)$ is the set of all mathematical functions $g$ such that $g(n)\leq c\,f(n)$ for some $c$ and all large enough $n$.

3. $O(f)$ is the set of all mathematical functions $g$ such that $g(n)\leq c\,f(n)$ for some $c$ and all large enough $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 $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 $c_2$ such that, for all large enough $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 $n$, the running time is between $c_2n^2$ and $c_1n^3$.

Answer 2

As I understand it, you've failed to account for asymtotic behaviour, but global behavior instead.

For example, we want $n + 1$ to be in $O(n^2 - n)$ because, once your inputs get big enough, the latter will always be slower than the former. But there is no $c$ where $\forall n \ldotp c \cdot n^2 - n \geq n + 1 $. Particularly, look at $n=1$. We want $c\cdot(1-1) \geq 1+1$, and there is no such value which will satisfy this.

That's the intuition for the actual definition. We want there to be some number $m$ where we say "there exists an $m$ and a $c$ where, for all $n>m$, we have $g(n) \geq c\cdot f(n)$" In our example, we'd set $m=2$, since once we get past that point, we can find a constant where $n^2-n$ is always bigger.

Also, be careful with your notation. What is $O(A)$? Big-O is an operation on functions, not on algorithms. You're better saying "let $f$ be the function where $f(n)$ is the maximum time $A$ takes on any input of size $n$", then saying $O(f)$.

Answer 3

We are not usually interested in what you call $O(A)$. This is the class of functions lower-bounding the time complexity of $A$, that is, they are functions $f$ such that $A$ runs in at least $Cf(n)$ steps. We're more usually interested in upper bounds on the running time, stating that $A$ runs in at most $Cf(n)$ steps. In your case, the running time is $O(n^2)$. It is also $O(n^3)$. Clearly the former bound is better. In general, we are interested in giving the best upper bound possible.

See also our reference question on Landau notation, if you can find it!

Answer 4

What you have defined there is linear dominance. It is indeed a reasonable definition for an $O$ but not the definition most people use.

We usually use Landau's $O$ which ignores any finite prefix of the functions at hand. That is because we have been trained to think that only behaviour for $n \to \infty$ matters. While that perspective has some advantages it is certainly not perfect.

For example, we want to assign the same "order of growth" to $10 n^2 + 5$ and $7 n^2 + 20$, that is they should be in each other's resp. $O$-class. That same class now also includes $10^{100} n^2 + 2^{100}$, though.

If you want to learn more about issues with Landau notation and different candidate definitions, I recommend the recent work by Rutanen et al. [1]. It's a rather mathematical read.

---

1. A General Definition of the O-Notation for Algorithm Analysis by K. Rutanen et al. (2015)