HiveBrain v1.2.0
Get Started
← Back to all entries
snippetCritical

O(·) is not a function, so how can a function be equal to it?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
canequalfunctionhownot

Problem

I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.

I understand semantics of it. But $T(n)$ and $O(f(n))$ are two different things.

$T(n)$ is an exact number, But $O(f(n))$ is not a function that spits out a number, so technically we can't say $T(n)$ equals $O(f(n))$, if one asks you what's the value of $O(f(n))$, what would be your answer? There is no answer.

Solution

Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a conventional way to write that $T(n) \in O(f(n))$.

Note that this also clarifies some caveats of the $O$ notation.
For example, we write that $(1/2) n^2 + n = O(n^2)$, but we never write that $O(n^2)=(1/2)n^2 + n$. To quote Donald Knuth (The Art of Computer Programming, 1.2.11.1):


The most important consideration is the idea of one-way equalities. [...] If $\alpha(n)$ and $\beta(n)$ are formulas that involve the $O$-notation, then the notation $\alpha(n)=\beta(n)$ means that the set of functions denoted by $\alpha(n)$ is contained in the set denoted by $\beta(n)$.

Context

StackExchange Computer Science Q#101324, answer score: 108

Revisions (0)

No revisions yet.