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 👁 Rendered by QuickLaTeX.com
with the value of 10000 and then prints it:

algorithm initializeAndPrintVariable:
 // INPUT
 // None
 // OUTPUT
 // Initialize a variable with a big number and print it.

 n <- 10000
 print n

This code executes in a fixed amount of time regardless of the value of 👁 Rendered by QuickLaTeX.com
, and the time complexity for the algorithm is 👁 Rendered by QuickLaTeX.com
. Alternatively, we can print the 👁 Rendered by QuickLaTeX.com
variable three times using a for loop:

algorithm initializeAndPrintVariableThrice:
 // INPUT
 // None
 // OUTPUT
 // Initialize a variable with a big number and print it several times.

 n <- 10000
 for i in range(1, 4):
 print n

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 👁 Rendered by QuickLaTeX.com
. We denote algorithms with constant time as 👁 Rendered by QuickLaTeX.com
. Regardless of the input size 👁 Rendered by QuickLaTeX.com
, it takes three times as long as usual. Therefore, 👁 Rendered by QuickLaTeX.com
, 👁 Rendered by QuickLaTeX.com
, or even 👁 Rendered by QuickLaTeX.com
are the same thing as 👁 Rendered by QuickLaTeX.com
.

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:

algorithm binarySearch(A, x):
 // INPUT
 // A = Sorted array
 // x = Target value
 // OUTPUT
 // Index of x in A, or -1 if not found

 low <- 0
 high <- len(A) - 1
 while low <= high:
 mid <- (low + high) / 2
 if A[mid] < x:
 low <- mid + 1
 else if A[mid] > x:
 high <- mid - 1
 else:
 return mid
 return -1

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 👁 Rendered by QuickLaTeX.com
function, where 👁 Rendered by QuickLaTeX.com
is the number of elements in the array. For example, when 👁 Rendered by QuickLaTeX.com
is 8, the while loop will iterate for 👁 Rendered by QuickLaTeX.com
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 👁 Rendered by QuickLaTeX.com
values, with 👁 Rendered by QuickLaTeX.com
provided as input:

algorithm numberCounter(n):
 // INPUT
 // n = Input value
 // OUTPUT
 // Print numbers from 1 to n

 for i <- 1 to n:
 print i

In this example, the number of iterations is directly proportional to the input size, 👁 Rendered by QuickLaTeX.com
. As 👁 Rendered by QuickLaTeX.com
increases, the time taken to execute the algorithm increases linearly. Therefore the algorithm’s time complexity is 👁 Rendered by QuickLaTeX.com
. When denoting the time complexity, we don’t discriminate between 👁 Rendered by QuickLaTeX.com
or 👁 Rendered by QuickLaTeX.com
as both have 👁 Rendered by QuickLaTeX.com
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:

algorithm allCombinationsOfTwoNumbers(n):
 // INPUT
 // n = Input value
 // OUTPUT
 // Prints all pairs of numbers from 1 to n

 for i <- 1 to n:
 for j <- 1 to log(n):
 print(i, j)

In this example, the outer loop runs 👁 Rendered by QuickLaTeX.com
times, and the inner loop runs 👁 Rendered by QuickLaTeX.com
times. Since the loops are nested, the total number is 👁 Rendered by QuickLaTeX.com
, and we denote the time complexity of the algorithm as 👁 Rendered by QuickLaTeX.com
. Another example of an N log N time algorithm is the Quicksort algorithm.

7. Polynomial Time Algorithms – O(n^m)

Next, we’ll delve into the topic of Polynomial-time algorithms, including algorithms with complexities such as 👁 Rendered by QuickLaTeX.com
, 👁 Rendered by QuickLaTeX.com
, and, more generally, 👁 Rendered by QuickLaTeX.com
, where 👁 Rendered by QuickLaTeX.com
is an integer. It’s important to note that compared to N log N algorithms, polynomial algorithms are relatively slower. Within the polynomial algorithms, 👁 Rendered by QuickLaTeX.com
is the most efficient, with 👁 Rendered by QuickLaTeX.com
, 👁 Rendered by QuickLaTeX.com
, and so on being successively slower.

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

algorithm allPermutationsOfTwoNumbers(n):
 // INPUT
 // n = Input value
 // OUTPUT
 // Prints all pairs of numbers from 1 to n

 for i <- 1 to n:
 for j <- 1 to n:
 print(i, j)

In this example, the outer loop runs 👁 Rendered by QuickLaTeX.com
times while the inner loop runs 👁 Rendered by QuickLaTeX.com
. Since the loops are nested, the total number of iterations is 👁 Rendered by QuickLaTeX.com
.

Another example of a polynomial time algorithm with a complexity of 👁 Rendered by QuickLaTeX.com
would be the following:

algorithm allPermutationsOfThreeNumbers(n):
 // INPUT
 // n = Input value
 // OUTPUT
 // Prints all triplets of numbers from 1 to n

 for i <- 1 to n:
 for j <- 1 to n:
 for k <- 1 to n:
 print(i, j, k)

Here, the total number of iterations is 👁 Rendered by QuickLaTeX.com
. In this case, there are three nested loops, each running 👁 Rendered by QuickLaTeX.com
times. Thus the computational complexity is 👁 Rendered by QuickLaTeX.com
.

8. Exponential Time Algorithms – O(kⁿ)

Let’s analyze algorithms with exponent-dependent inputs, like 👁 Rendered by QuickLaTeX.com
. Their runtime increases significantly as the input size grows. Specifically, the algorithm’s runtime doubles with each additional input when 👁 Rendered by QuickLaTeX.com
is 2. For instance, if 👁 Rendered by QuickLaTeX.com
equals 2, the algorithm will run four times; if 👁 Rendered by QuickLaTeX.com
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 👁 Rendered by QuickLaTeX.com
triple their runtime with each added input. In general, algorithms with complexities of 👁 Rendered by QuickLaTeX.com
increase their runtime by a factor of 👁 Rendered by QuickLaTeX.com
with each additional input.

Let’s have a look at a simple example of an 👁 Rendered by QuickLaTeX.com
time algorithm:

algorithm decimalToBinaryEnumerator(n):
 // INPUT
 // n = Input value
 // OUTPUT
 // Print numbers from 1 to n in the binary format

 for i <- 1 to 2^n:
 print binary(i)

In this example, the for loop runs 👁 Rendered by QuickLaTeX.com
times, printing every binary number from 1 to 👁 Rendered by QuickLaTeX.com
. 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 👁 Rendered by QuickLaTeX.com
cities, there are 👁 Rendered by QuickLaTeX.com
possible permutations, and thus the brute-force approach has an 👁 Rendered by QuickLaTeX.com
runtime complexity.

While explaining the solution to this problem is outside the scope of this article, we can demonstrate a simple 👁 Rendered by QuickLaTeX.com
algorithm that prints all the numbers from 0 to 👁 Rendered by QuickLaTeX.com
at each iteration of the factorial number:

algorithm simulationOfFactorialTime(n):
 // INPUT
 // n = Integer
 // OUTPUT
 // Prints all numbers from 0 to each factorial of a number n

 for i <- 1 to n!:
 print i

In this example, the number of recursive calls grows with the factorial of the input size, thus resulting in a runtime complexity of 👁 Rendered by QuickLaTeX.com
.

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.