Asymptotic runtime complexity: How to gauge algorithm efficiency

What is an algorithm#

An algorithm refers to a sequence of steps that solves a given problem. To that end, an algorithm takes some input(s) and produces desired output(s). For example, below is the input and the corresponding output of a typical sorting algorithm:

Input: An array of numbers $[a_1, a_2, \cdots, a_n]$

Output: A sorted array of numbers $[\hat{a_1}, \hat{a_2},\cdots, \hat{a_n}]$, where $\hat{a_i} \leq \hat{a}_{i+1}, \forall i$

An algorithm is considered correct if and only if, on all the possible inputs, it produces the desired output(s). For instance, a sorting algorithm that always sorts an array of numbers successfully for all the possible inputs will be considered correct.

Independent time complexity#

When we implement an algorithm in a programming language (such as Java or C), it becomes a program and can be executed on various hardware platforms. Different algorithms designed to solve the same problem usually differ widely in their time complexities. This difference may change drastically or be skewed when these algorithms are implemented in different programming languages and are executed on different hardware platforms. For instance, in general, an algorithm implemented in Assembly language would execute faster than its Python implementation. Similarly, an algorithm (say Algo-n) running on a supercomputer will be faster than another algorithm (Algo-m) running on an old resource-constrained PC. This might be true even when Algo-m is theoretically more efficient than Algo-n.

We cannot fairly compare algorithms’ efficiency by executing their implementations and recording their runtime.

Therefore, computer scientists and programmers are interested in knowing an algorithm’s time complexity independent of its implementation’s language and execution time on any hardware platform.

Time complexity as function of input’s size#

Most algorithms’ time complexity will increase as their input size increases. For instance, if the input to the find_min algorithm is an array of size 10, it will run faster as compared to when its input is an array containing 1 million elements.

If Algo-1 is faster on smaller inputs than Algo-2 but slower on large inputs, will the Algo-1 be considered more efficient?

In computer science, we are interested in the time complexity of an algorithm as a function of the size of its input. That is, how the time complexity of an algorithm grows with respect to the increase in its input size. Thus, an algorithm (in this case Algo-2) that is generally more efficient on the larger input sizes is considered superior.

Calculating time complexity#

We aim to measure an algorithm’s time complexity independent of its implementation and any hardware platform. To that end, we assume that each pseudocode instruction will take a constant amount of time. In particular, $i^{th}$ pseudocode instruction will take $c_i$ time to execute, where $c_i$ is a positive integer. We will carefully calculate how many times each instruction will execute. Then we calculate the total time taken by each instruction as:

Total time of Instruction-i = constant time taken by it, $c_i$ $\times$ number of times it will be executed

Finally, we add the total time taken by all the instructions of the pseudocode, to calculate the time taken by our algorithm.

Let’s make it crystal clear by calculating the time of our find_min pseudocode given earlier.

$$\begin{align*} T(n) &= c_1+c_2+nc_3+(n-1)c_4+k c_5+c_6 \\ &= (c_1+c_2-c_4+c_6)+n(c_3+c_4)+k c_5\\ &= a+nb+kc \end{align*}$$

In the equation above, $a=c_1+c_2-c_4+c_6$, $b=c_3+c_4$, and $c=c_5$. Furthermore, the value of $k$ depends on the kind of input. We can understand the concept of the worst case and the best case behavior of the algorithm with the possible values the constant $k$ may take.

The best case occurs when the minimum integer will be the first element of the array. Hence, the if-condition will never be true. Thus, the value of $k$ in the best case will be zero, and $T(n)=a+nb$. Whereas in the worst case the input array will be sorted in descending order. Hence, the if-condition will always be true, making the value of $k$ in the worst case $n$, $T(n)=a+nb+nc$.

Asymptotic time complexity#

In the last section, we learned to find the running time of iterative algorithms. However, we may have two algorithms with different running times:

We cannot say which one is better without having to calculate the exact values of constants $a$, $b$, $d$, $e$, and $f$. However, these constant values will not be independent of the implementation language and hardware platform. Furthermore, finding their exact values will be too cumbersome. Thus, we resort to asymptotic time complexity. In asymptotic time complexity, our focus is on the order of growth of the running time corresponding to the increase of the input size. Big O, Big Theta, and Big Omega are three key notations that describe asymptotic time complexity.

Big O: The upper bound#

Given that a running time of an algorithm is $T(n)=f(n)$, where $n$ is the size of the input, we say that function f is big O of a function g, written as:

$$f(n) = O(g(n))\text{,}$$

if there exist positive constants $c, n_0 \in \R$ such that

$$\begin{align*} f(n) \le c g(n),\ \ \forall n \ge n_0 \end{align*}\text{.}$$

In simple words, the above equation implies that when the size of input $n \ge n_0$, the time of the algorithm $f(n)$ will be upper bounded by $c g(n)$. That is, $f(n)$ will be equal to or less than $c g(n)$ on all the input’s sizes $n \ge n_0$. This is depicted by the following graphical illustration.

If $f(n) = O(n^i)$, for any integer $i$, then by the above definition, the following statement will always be true:

$$\begin{equation*} f(n) = O(n^j), \forall j \ge i \end{equation*}$$

Big Omega: The lower bound#

Given that a running time of an algorithm is $T(n)=f(n)$, where $n$ is the size of the input, we say that function f is Big Omega of a function g, written as:

$$f(n) = \Omega(g(n))\text{,}$$

when there exist positive constants $c, n_0 \in \R$, such that

$$f(n) \ge c g(n),\ \ \forall n \ge n_0\text{.}$$

In simple words, the above equation implies that when the size of input $n \ge n_0$, the time of the algorithm $f(n)$ will be lower bounded by $c g(n)$. That is, $f(n)$ will be equal to or greater than $c g(n)$ on all the input’s sizes $n \ge n_0$, as depicted by the following illustration.

If $f(n) = \Omega(n^i)$, for any integer $i$, then by the above definition, the following statement will always be true:

$$\begin{equation*} f(n) = \Omega(n^j), \forall j \le i \end{equation*}$$

Big Theta: The tight bound#

Big Theta is the most useful asymptotic notation and should be used in place of Big O and Big Omega whenever possible. It is because it represents the tight bound of running time and provides much more information about an algorithm’s complexity than its counterparts.

Given that a running time of an algorithm is $T(n)=f(n)$, where $n$ is the size of the input, we say that function f is Big Theta of a function g, written as:

$$f(n) = \Theta(g(n))\text{,}$$

if there exist positive constants $c_1, c_2, n_0 \in \R$ such that

$$c_2 g(n) \le f(n) \le c_1 g(n),\ \ \forall n \ge n_0 \text{.}$$

In simple words, the above equation implies that $f(n)=\Theta(g(n))$ as well as $f(n)=O(g(n)$ for input size $n \ge n_0$, with constants $c_1$ and $c_2$, respectively. In other words, $f(n)$ will be equal to or less than $c_1(g(n))$ as well as equal to or greater than $c_2(g(n))$ on all the input’s size $n \ge n_0$. This is depicted by the following graphical illustration.

Example: Insertion sort#

Let’s go through an example to make all the concepts clear. Insertion sort is a famous sorting algorithm that is similar to the typical sorting of cards.

In Insertion sort, we assume that our input array is divided into two parts: sorted elements and unsorted elements. Initially, the sorted array has only a single element, whereas the unsorted array has the rest of the elements. We remove an element from the unsorted part of the array and find the place to insert it at the correct location in the already sorted array. This process continues until the unsorted part becomes empty. The pseudocode of Insertion sort is given below:

Insertion sort running time#

$$\begin{align*} T(n) &= c_1+ c_2 n+ c_3 (n-1)+c_4 (h(j))+ c_5 (h(j)-1)+c_6 (n-1)\\ &= (c_2+c_3)n + (c_4+c_5)h(j)+ (c_1-c_3-c_5-c_6)\\ &= an+bh(j)+c \end{align*}$$

Where, constants $a=c_2+c_3$, $b=c_4+c_5$, and $c=c_1-c_3-c_5-c_6$

Best-case analysis#

In the best case, the condition $A[j] > \text{toInsert}$, is never true. That is, in this case, the input array is already sorted. Thus, in the best case $h(j)=1$. The running time becomes:

$$T(n) = an+b+c = an+d$$

We claim that $T(n)=\Theta(n)$. To prove that claim, we have to show that $T(n)=O(n)$ and $T(n)=\Omega(n)$. Let’s verify it quickly.

To show that $T(n)=O(n)$, we have to find a positive constant $c_1$ such that $an+d \le c_1n$. One such possibility could be $c_1=|a|+|d|$. For all $n>=1$ the above inequality holds, proving that $T(n)=O(n)$.

To show that $T(n)=\Omega(n)$, we have to find a positive constant $c_2$ such that $an+d \ge c_2n$. One possibility could be $c_2=1$. For all $n>=1$ the above inequality holds, proving that $T(n)=\Omega(n)$.

Thus, proving that the best-case complexity analysis of Insertion sort is $\Theta(n)$.

Worst-case analysis#

In the worst case, the condition $A[j] > \text{toInsert}$, will always be true. In this case, the input array is reversely sorted (descending order). In our pseudocode, the loop (of line number 8) will always run from $j=i-1$ to 0. Therefore, $h(j)=1+2+3+\cdots+n$. We can calculate this sum using the sum of arithmetic series formula, $h(j)=\frac{n}{2}(1+n)=\frac{n}{2}+\frac{n^2}{2}$. Thus,

$$T(n) = a\bigg(\frac{n}{2}+\frac{n^2}{2}\bigg)+c+b = an+d$$

We claim that according to the above equation, the worst-case running time of Insertion sort is $T(n)=\Theta(n^2)$. We can easily prove it using arguments similar to the best-case proof. However, we are leaving it to the readers.

Time complexities of sorting algorithms#

Let’s conclude this blog by presenting the best- and the worst-case complexity of some of the famous sorting algorithms, given that they take an array of size $n$ as input.

Quiz: Test your understanding#

Increase your algorithm proficiency today#

At this point, you should have a pretty good understanding of the importance of calculating an algorithm’s efficiency, how to do so, the reasons for using asymptotic time complexity, and the differences between its key notations.

In case you want to learn about algorithms, and their time complexities, in more detail, then you’ll find a plethora of interactive and exciting courses available at Educative. If you’re relatively new to this subject, consider the course Data Structures and Algorithms in Python, which covers these fundamental computer science concepts using Python, an essential language for developers and data scientists alike. If you know a little Java and are looking to take the next step in your career, we’d suggest checking out the course Algorithms for Coding Interviews in Java.

Happy learning!

• Top data structures and algorithms every developer must know
• Ace the top 15 Java algorithm questions for coding interviews
• Algorithms 101: How to check if a string is a palindrome