1. Overview

In this tutorial, we’ll talk about what Big O Notation means. Then, we’ll review a few examples to investigate its effect on running time.

2. The Intuition of Big O Notation

Big O Notation is an efficient way to evaluate algorithm performance. The study of the performance of algorithms – or algorithmic complexity – falls into the field of algorithm analysis. This method calculates the resources (e.g., disk space or time) needed to solve the assigned problem. Here, we?ll focus primarily on time, where the faster an algorithm can complete a task, the more efficient it is.

Big O notation helps us analyze how the input size affects an algorithm’s running time. To understand Big O, it is essential to know the growth rate. This refers to the amount of time needed for each input size.

Next, we?ll study some algorithms and evaluate their time complexity.

3. Constant Time Algorithms – O(1)

First, let’s see a simple algorithm that initializes a variable n with the value of 10000 and then prints it:

    \[\begin{algorithm}[H] \setcounter{algocf}{0} \SetAlgoLined \KwData{Initial state} \KwResult{Initialize a variable with a big number and print it.} n $\gets${10000}\; \textbf{print} n\; \caption{Initializing and printing a variable} \end{algorithm}\]

This code executes in a fixed amount of time regardless of the value of n, and the time complexity for the algorithm is O(1). Alternatively, we can print the n variable three times using a for loop:

    \[\begin{algorithm}[H] \setcounter{algocf}{1} \SetAlgoLined \KwData{Initial state} \KwResult{Initialize a variable with a big number and print it thrice. } n $\gets$ 10000\; \For{i in range(1, 4)}{ \textbf{print} n; } \caption{Initilizing and printing a variable 3 times} \end{algorithm}\]

The above example is also constant time. Even if it takes three times as long to run, it doesn’t depend on the input size n. We denote algorithms with constant time as O(1). Regardless of the input size n, it takes three times as long as usual. Therefore, O(2), O(3), or even O(1000) are the same thing as O(1).

We don’t care about how long it takes to run, only that it takes constant time.

4. Logarithmic Time Algorithms – O(log(n))

Asymptotically, constant time algorithms are the quickest. Next comes algorithms that have a logarithmic time complexity. However, they are more challenging to visualize.

One typical example of a logarithmic time algorithm is the binary search algorithm:

    \[\begin{algorithm}[H] \setcounter{algocf}{2} \SetAlgoLined \KwData{Sorted array A, and target value x} \KwResult{Index of x in A, or -1 if not found} low $\gets$ 0\; high $\gets$ len(A) - 1\; \While{low $\leq$ high}{ mid $\gets$ (low + high) / 2\; \If{A[mid] $<$ x}{ low $\gets$ mid + 1\; } \ElseIf{A[mid] $>$ x}{ high $\gets$ mid - 1\; } \Else{ \Return mid\; } } \Return  -1\; \caption{Binary Search} \end{algorithm}\]

In binary search, the input is the array size the algorithm splits in half on each iteration until it finds the target value or -1 if absent. Thus, the running time is proportional to the log_2(n) function, where n is the number of elements in the array. For example, when n is 8, the while loop will iterate for log_2(8) = 3 times.

5. Linear Time Algorithms – O(n)

Next, we’ll look at linear time algorithms whose time complexity is proportional to the size of their inputs.
For instance, consider the following pseudocode of an algorithm that enumerates the n values, with n provided as input:

    \[\begin{algorithm}[H]  \setcounter{algocf}{3} \SetAlgoLined \KwData{Input value n} \KwResult{Print numbers from 1 to n} \For{i in range(1, n + 1)}{ \textbf{print} i; }\caption{Number Counter} \end{algorithm}\]

In this example, the number of iterations is directly proportional to the input size, n. As n increases, the time taken to execute the algorithm increases linearly. Therefore the algorithm’s time complexity is O(n). When denoting the time complexity, we don’t discriminate between 0.1n or (1000n+1000) as both have O(n) time complexity and grow directly related to the input size.

6. N Log N Time Algorithms – O(n log n)

The N log N algorithms perform worse than algorithms having linear time complexity. This is because their running time increases linearly and logarithmically with the input size. For example, let’s see the following algorithm with for loops:

    \[\begin{algorithm}[H]  \setcounter{algocf}{4} \SetAlgoLined \KwData{Input value n} \KwResult{Print all pairs of numbers from 1 to n} \For{i in range(1, n + 1)}{ \For{j in range(1, log(n) + 1)}{ \textbf{print} (i, j); } } \caption{All Combinations of two numbers}\end{algorithm}\]

In this example, the outer loop runs n times, and the inner loop runs log(n) times. Since the loops are nested, the total number is n * log(n), and we denote the time complexity of the algorithm as O(n*log(n)). Another example of an N log N time algorithm is the Quicksort algorithm.

7. Polynomial Time Algorithms – O(nm)

Next, we’ll delve into the topic of Polynomial-time algorithms, including algorithms with complexities such as O(n^2), O(n^3), and, more generally, O(n^m), where m is an integer. It’s important to note that compared to N log N algorithms, polynomial algorithms are relatively slower. Within the polynomial algorithms, O(n^2) is the most efficient, with O(n^3), O(n^4), and so on being successively slower.

Let’s have a look at a simple example of a quadratic time algorithm using for loops:

    \[\begin{algorithm}[H]  \setcounter{algocf}{5} \SetAlgoLined \KwData{Input value n} \KwResult{Print all pairs of numbers from 1 to n} \For{i in range(1, n + 1)}{ \For{j in range(1, n + 1)}{ \textbf{print} (i, j); } } \caption{All Permutations of 2 numbers}\end{algorithm}\]

In this example, the outer loop runs n times while the inner loop runs n. Since the loops are nested, the total number of iterations is n^2.

Another example of a polynomial time algorithm with a complexity of O(n^3) would be the following:

    \[\begin{algorithm}[H]  \setcounter{algocf}{6} \SetAlgoLined \KwData{Input value n} \KwResult{Print all triplets of numbers from 1 to n} \For{i in range(1, n + 1)}{ \For{j in range(1, n + 1)}{ \For{k in range(1, n + 1)}{ \textbf{print} (i, j, k); } } } \caption{All Permutations of 3 numbers}\end{algorithm}\]

Here, the total number of iterations is n^3. In this case, there are three nested loops, each running n times. Thus the computational complexity is O(n^3).

8. Exponential Time Algorithms – O(kn)

Let’s analyze algorithms with exponent-dependent inputs, like O(2^n). Their runtime increases significantly as the input size grows. Specifically, the algorithm’s runtime doubles with each additional input when k is 2. For instance, if n equals 2, the algorithm will run four times; if n equals 3, the algorithm will run eight times. This behavior contrasts logarithmic time algorithms, which have a runtime that decreases with each additional input. Additionally, algorithms with complexities of O(3^n) triple their runtime with each added input. In general, algorithms with complexities of O(k^n) increase their runtime by a factor of k with each additional input.

Let’s have a look at a simple example of an O(2^n) time algorithm:

    \[\begin{algorithm}[H] \setcounter{algocf}{7} \SetAlgoLined \KwData{Input value n} \KwResult{Print numbers from 1 to n in binary} \For{i in range(0, 2^{n})}{ \textbf{print} binary(i)\; } \caption{Decimal to Binary enumarator} \end{algorithm}\]

In this example, the for loop runs 2^n times, printing every binary number from 0 to (2^n) - 1. A typical example of an exponential time algorithm is the Recursive Fibonacci Sequence.

9. Factorial Time Algorithms – O(n!)

Finally, let’s analyze algorithms with a factorial runtime, our worst-case scenario. This class of algorithms has a runtime that increases proportionally with the factorial of the input size. A well-known example is solving the traveling salesman problem using a brute-force approach.

In short, the traveling salesman problem involves finding the shortest route that visits each city in a given list exactly once and returns to the starting city. Unfortunately, for a list of n cities, there are n! possible permutations, and thus the brute-force approach has an O(n!) runtime complexity.

While explaining the solution to this problem is outside the scope of this article, we can demonstrate a simple O(n!) algorithm that prints all the number from 0 to n! at each iteration of the factorial number:

    \[\begin{algorithm}[H]  \setcounter{algocf}{8} \SetAlgoLined \KwData{Integer n} \KwResult{Prints all numbers from 0 to each factorial of a number n} \For{i = 1 \KwTo factorial(n)}{ \textbf{print} i\; } \caption{Simulation of O(n!)}\end{algorithm}\]

In this example, the number of recursive calls grows with the factorial of the input size, thus resulting in a runtime complexity of O(n!).

10. Asymptotic Functions

The Big O notation belongs to a class of asymptotic functions that we use to study the performance of algorithms. While the Big O notation disregards the efficiency of algorithms with small input sizes, it is primarily concerned with the behavior of algorithms on significant inputs.

Additionally, there are two other asymptotic functions to describe algorithm performance at the limit: Big ? and Big ? notations.

For example, the Big O notation defines the algorithms that perform no worse than a certain speed denoting the upper bound. Instead, the Big ? notation defines the algorithms that perform no better than a certain speed indicating the lower bound. Finally, The Big ? notation indicates an algorithm operating at a constant speed that we can see as equality.

Big O, Big ?, and Big ? notations are used to describe the performance of algorithms, with Big O being the most common. They help understand the effect of input size on an algorithm’s performance and can be used to determine the best algorithm based on the input size.

11. Visualizing Different Complexities

All the time complexities presented are easier to visualize if we plot them on a graph with their input size and their time complexity:

Various complexity classes

Above, we can appreciate the need to reduce the complexity of algorithms.

12. Conclusion

In this article, we discussed the importance of understanding time complexity and analyzing algorithm performance using the Big O notation. We also examined time complexities, such as constant, logarithmic, linear, linearithmic, polynomial, exponential, and factorial time algorithms.

We can use the following cheat sheet to explore the time complexity for typical data structures.

Comments are closed on this article!