The Time Complexity – Big O Notation

Big O notation is a crucial concept in computer science – a great tool for expressing the efficiency of an algorithm. Big O notation is a way of describing the time complexity or space complexity of an algorithm or function. In this article, we will explore the basics of the time complexity of Big O notation, its significance, and how it helps in designing efficient algorithms.

A simple way to understand the time complexity – big O notation

Big O achieves consistency by focusing on the number of steps an algorithm takes, but in a specific way. The time complexity refers to the amount of time an algorithm takes to solve a problem as the size of the input increases. It is usually measured in terms of the number of operations or steps the algorithm takes to solve the problem.

When we perform an algorithm with the input N data elements, how many steps will the algorithm take?

Let’s take example of linear search. If we have N data elements in an array, how many steps will linear search takes?

Because linear search checks every element in a list or array until it finds the target value or reaches the end of the list, linear search will take N steps, and we express this as O(N), an algorithm that is O(N) is also known as having linear time. Linear search is best used for small lists or unsorted data.

O(N) describes exactly how the number of steps increase as the data increases.

Note that linear search isn’t always O(N) because if the item we’re searching for is found in the first cell, linear search in this case just takes 1 step.

Here is an code example that describe the time complexity of O(N):

function printNumbers(n) {
  for (let i = 1; i <= n; i++) {
    console.log(i);
  }
}

This function prints the numbers from 1 to n by iterating through a loop n times. As the input size n grows, the time required to execute the loop grows linearly. Therefore, the time complexity of this function is O(n).

How about the time complexity with Big O Notation of reading from a standard array?

The answer is O(1) because no matter how many N elements the array has, reading from an array always takes just 1 step.

O(1) is considered the fastest kind of algorithm, and it isn’t affected by increased data.

Look at this code example:

function printElementAtIndex2(arr) {
  console.log(arr[2]);
}
printElementAtIndex2([1, 5, 7]); // This will print 7

In this example, the function takes an input array [1, 5, 7] and prints out the element at index 2, which is 7. The function has a time complexity of O(1) since it performs a single operation to retrieve the element at a fixed index.

So far, we’ve mentioned about O(N) and O(1). What about O(log N)?

function binarySearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;
    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      if (arr[mid] === target) {
        return mid;
      } else if (arr[mid] < target) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return -1;
};

const arr = [1, 3, 5, 7, 9];
const target = 7;

const resultIndex = binarySearch(arr, target);
if (resultIndex === -1) {
  console.log("The target value ${target} was not found in the array.");
} else {
  console.log("The target value ${target} was found at index ${resultIndex}.");

Big O notation is commonly used in computer science to compare the efficiency of algorithms and to choose the most appropriate algorithm for a specific problem. It is also used to estimate the scalability of a system and to predict how it will perform as the size of the input increases.

understanding the time complexity is an important concept for any programmer who wants to write efficient and scalable code. By analyzing the worst-case time required for an algorithm to run as a function of the input size, we can estimate how the algorithm will perform on large datasets and identify opportunities for optimization.