Return to Answer

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 issues of the $O$ notation as it is normally used. For example, $n^2 \in O(n^3)$ but $n^3 \notin O(n^2)$. So you could write $O(n^2) = O(n^3)$, but you cannot write $O(n^3) = O(n^2)$, even though one normally expects $=$ to represent an equivalence relation (in particular, symmetric).

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

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 simplified way to write that $T(n) \in O(f(n))$.

Note that this also clarifies some issues of the $O$ notation as it is normally used. For example, $n^2 \in O(n^3)$ but $n^3 \notin O(n^2)$. So you can write $O(n^2) = O(n^3)$, but you cannot write $O(n^3) = O(n^2)$, even though one normally expects $=$ to represent an equivalence relation (in particular, symmetric).

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 issues of the $O$ notation as it is normally used. For example, $n^2 \in O(n^3)$ but $n^3 \notin O(n^2)$. So you could write $O(n^2) = O(n^3)$, but you cannot write $O(n^3) = O(n^2)$, even though one normally expects $=$ to represent an equivalence relation (in particular, symmetric).

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 simplified way to write that $T(n) \in O(f(n))$.

Note that this also clarifies some issues of the $O$ notation as it is normally used. For example, $n^2 \in O(n^3)$ but $n^3 \notin O(n^2)$. So you can write $n^2 = O(n^3)$, but you cannot write $n^3 = O(n^2)$.

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 simplified way to write that $T(n) \in O(f(n))$.

Note that this also clarifies some issues of the $O$ notation as it is normally used. For example, $n^2 \in O(n^3)$ but $n^3 \notin O(n^2)$. So you can write $O(n^2) = O(n^3)$, but you cannot write $O(n^3) = O(n^2)$, even though one normally expects $=$ to represent an equivalence relation (in particular, symmetric).