Understanding Big O Notation in time complexity is important to write more efficient and scalable code. Also it is a common question asked in the technical interviews. This article aims to provide a comprehensive understanding of the most common time complexity scenarios with examples. At the end of this article, you will have much better ideas of what Big O Notation is and how it works.

What is Big O Notation?

According to Wikipedia, “In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.”

Big O notation is a mathematical expression representing of how the runtime of an algorithm grows as the inputs size increases to the worst case scenario such as infinity.

The common Big O notations are:

O(1) – Constant
O(log n) – Logarithmic
O(n) – Linear
O(nlog n) – Linearithmic
O(n^2) – Quadratic
O(n^3) – Cubic
O(2^n) – Exponential
O(n!) – Factorial

Let’s discover each notation with examples.

In graph

When we draw the Big O notations on the graph, it looks like below:

Bit O Notation graph — Big O Notation graph

The O in Big O means ‘order of’ and n represents the number of inputs. The JS interview will check if we understand what will happen when n approaches infinity and provide efficient algorithms to solve the given problems.

Big O notation is used to describe the time complexity (the runtime of an algorithm as the size of the inputs increases) or the space complexity (the additional memory space we need to allocated by our algorithm).

In this article, we will take a look at the time complexity first and in the future article, I will publish the space complexity.

O(1) – Constant time

Regardless of the size of input, it will always take the same amount of time to perform the algorithm.

function calcNum(n) {
  return n * (n + 6) / 2;
}

From the example code above, even if we increase the size of the input, n, there will always be 3 operations (*, + and /) and the execution time remains the same.

O(log n) – Logarithmic Time

The logarithmic time complexity is when the size of input n is increased, the runtime of the operations doesn’t get increased as much at each step of the algorithm.

From the above graph, when the input size n is small, the graph increases dramatically but when the input size n gets bigger, the curve gets flattened. It is opposite to the exponential time explained below.

The logarithmic time complexity is a common example of binary search algorithm. If you’re interested in understanding the mechanics of the binary search algorithm and how to code it yourself, take a look at this article where I explore the finer details of the binary search process.

The logarithmic time complexity is the second best performing algorithm after constant time and it is even better than linear time.

O(n) – Linear Time

For each additional input, the runtime of the function grows proportionally to the input size.

function findIndex(array, value) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === value) {
      console.log(i);
    }
  }
}

In the example, we are iterating through all values in the array, and when the length of the array increases n times, it takes exactly n times longer.

Let’s take a look at another example.

function findIndex(array, value) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === value) {
      console.log('Found index - counting up', i);
    }
  }

  for (let j = array.length - 1; j >= 0; j--) {
    if (array[i] === value) {
      console.log('Found index - counting down', j);
    }
  }
}

In this example, we have two loops in the function. Both first and second loop have the time complexity of O(n) so this results in O(2n). But we are looking at the big picture so at the end of the day, we don't really care about the constant factor of 2. What we're really interested in is the time complexity as the size of the input grows larger. Therefore, we can simplify the time complexity to O(n).

O(nlog n) - Linearithmic Time

The linearithmic time complexity is the n (linear time) multiplied by log n (logarithmic time). This time complexity gives us better performance than the quadratic time, O(n^2), but worse than the linear time, O(n).

A good examples of the linearithmic time complexity are the merge sort and quick sort algorithm. I am going to publish those sorting algorithms in the near future and we will talk more about the linearrithmic time complexity, but basically merge sort is dividing the array in two halves, sorting each halved array and then merging back them together.

O(n^2) - Quadratic Time

The time it takes to run the algorithm grows at the square of the number of inputs. A common example is nested loops. The below example is a bubble sort algorithm which compares the adjacent elements in an array and swap their positions if they are not in the right order.

function bubbleSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      if (array[j] > array[j + 1] {
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
}

In this example, the inner loop always runs n times when outer loop runs each time. If the input size is 2, the nested loops has to go through 2 * 2 or 2^2. If the input size is 8, it will take 64 which makes the input size quadratically affects the runtime of the algorithm.

O(n^3) - Cubic Time

The algorithm runs in cubic time as the input increases. For example, if the input size is 10, the runtime of the algorithm will be 10 * 10 * 10 = 1,000 which is worse than the quadratic time.

function cubicTime(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      for (let k = 0; k < array.length; k++) {
        // additional logic goes here
      }
    }
  }
}

The cubic time complexity is a very slow algorithm so less efficient for the larger inputs. An example above shows the cubic time complexity with 3 nested loops.

To improve the cubic time complexity, some of the ways are to use memoization or dynamic programming which I will talk more in the future articles.

O(2^n) - Exponential Time

As the input increases, the time to run the algorithm doubles. The most common example of the exponential time complexity is the recursive functions.

function fib(num) {
  if (num < 2) {
      return num;
  }

  return fib(num - 1) + fib(num - 2);
}

The above example is to find the nth number in the Fibonacci sequence with recursion and the size of the tree exponentially grows when num increases. Its growth doubles with each addition to the input size.

For the side note, we should use memoization to improve its efficiency and it’s commonly asked in the JavaScript interview.

O(n!) - Factorial Time

Factorial notation is the worst time complexity.

So what is factorial? According to Wikipedia, “In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n.”

For example, 5! = 5 * 4 * 3 * 2 * 1 = 120. How about 6!? It will be 6 * 5! = 720. One more additional input will dramatically increase the runtime. 7! = 7 * 6! = 5040.

A typical example of the factorial time complexity is the Travelling salesman problem (TSP), "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?".

For example, if we have 3 cities, Sydney, Melbourne and Brisbane, there are 6 permutations coming from 3!.

1) Sydney -> Melbourne -> Brisbane -> Sydney
2) Sydney -> Brisbane -> Melbourne -> Sydney
3) Melbourne -> Sydney -> Brisbane -> Melbourne
4) Melbourne -> Brisbane -> Sydney -> Melbourne
5) Brisbane -> Sydney -> Melbourne -> Brisbane
6) Brisbane -> Melbourne -> Sydney -> Brisbane

If we increase the number of cities to 10, then there will be 3,628,800 possible permutations making it impractical to calculate all possible permutations.

One of the ways to improve it is heuristic and approximation algorithm which provides good-enough results.

Conclusion

Understanding how to analyze the time complexity of your code using Big O Notation can help you design and optimize algorithms that are efficient and scalable. By choosing the right algorithm for the job, you can save precious computing resources and reduce the time it takes to execute your code.

It's essential to remember that the best performing algorithm is not always the fastest, but the one that scales well as the input size increases.

In this article, we covered the most common time complexities with examples of each time complexity and how they behave as the input size increases.

I hope you found this article on Big O Notation informative and useful. And if you prepare for technical interviews, remember to revisit this topic and continue practicing different time complexities with examples.