Misuses of the big-O notation

Misuses of the big-$O$ notation

Asymptotic analysis is an essential part of computational evaluations. It helps in analyzing algorithms with respect to their input sizes. It is not an exact measure of the running time but rather an approximation of how the time or cost increases with regard to the input size.

This analysis is done based on three cases:

• Best case

• Average case

• Worst case

The analysis is done for three bounds:

• Upper bound (big-$O$)

• Lower bound (big-$\Omega$)

• Tight bound (big-$Θ$)

What is big-$O$?

The big-$O$ notation defines the upper bound for an algorithm. It bounds the function from above. It is easier to find an upper bound by breaking down the algorithm into its subparts.

$T(n)$ is $O(f(n))$ if positive constants$c$ and $n_0$ exist, such that $T(n) \le c.f(n)$ for all $n \ge n_0$.

A pictorial representation of this is as follows:

What is big-$Θ$?

The big-$Θ$ notation bounds a function from above and below. This is used to define the exact asymptotic behaviors of an algorithm or its "tight" bounds. To get the theta notation of an algorithm, we ignore the low order terms and the constants.

$T(n)$ is $Θ(f(n))$ if positive constants $c_1$, $c_2$, and $n_0$ exist, such that $c_1.f(n) \le T(n) \le c_2.f(n)$ for all $n \ge n_0$.

A pictorial representation of this is as follows:

Problems

• The primary problem we face during this is the assignment of $O$ or $Θ$ to an algorithm. People often interchange big-$O$ with big-$Θ$, which changes the meaning of the obtained runtime.

• Another problem is that big-$O$ is written as $O(g(n)) = f(n)$. This is considered to be a misuse of the notation since the equality sign is misleading for some algorithms, as it indicates that there exists a symmetry. This symmetry does not exist in reality.

Examples

For the first example, let's take the function:

The bounds for this function are:

• $O(n^3)$, $O(n^2)$ as the upper bound

• $Θ(n^2)$ as the tight bound

Let's take the other function as:

The bounds for this function are:

• $O(n^4)$, $O(n^3)$ as the upper bound

• $Θ(n^3)$ as the tight bound

The misuse here is that $f(n) =\ O(n^3) =\ g(n)$ but, $f(n) \neq g(n)$.

For the second example, let's take

The above holds and is true but

This shows the relationship is not symmetric.

In terms of the equations, the class of functions with complexity $n$ is included in the class of functions with complexity $n^2$. This can be explained as a function with a linear upper bound as complexity is also a function with an upper quadratic complexity bound. Moreover, the quadratic bound is not very tight.

Note: This issue occurs because we use the notation $T(n) = O(f(n))$, while a better notation would be $T(n) \in O(f(n))$.