Understanding Big O Notation (with JavaScript Code Examples)

Big O notation is a way to describe the performance of an algorithm, specifically in terms of its time complexity (how long it takes to run) and sometimes its space complexity (how much memory it uses). It provides an upper bound on the running time of an operation in the worst case, helping us to understand how the algorithm will perform as the input size grows.

Here are some JavaScript code examples to illustrate different Big O complexities:

O(1) - Constant Time:

The running time is constant and does not depend on the size of the input.

  function getFirstElement(arr) {
    return arr[0];
  }

No matter how large the array arr is, this function takes the same amount of time to execute.

O(n) - Linear Time

The running time increases linearly with the size of the input.

  function findElement(arr, target) {
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] === target) {
        return true;
      }
    }
    return false;
  }

In the worst case, this function will loop through all n elements of the array to find the target.

O(n^2) - Quadratic Time

The running time is proportional to the square of the size of the input.

function hasDuplicate(arr) {
  for(let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        return true;
      }
    }
  }
  return false;
}

For an array of size n, this function checks each pair of elements, resulting in roughly n^2 checks.

O(log n) - Logarithmic Time

The running time grows logarithmically as the size of the input increases.

  function binarySearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;

    while (low <= high) {
      const mid = Math.floor((low / high) / 2);
      if (arr[mid] === target) {
        return true;
      }
      if (arr[mid] < target) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    return false;
  }

In binary search, the size of the remaining elements to be searched gets halved each step, resulting on a logarithmic number of steps.

O(n log n) - Linearithmic Time

Often seen in more efficient sorting algorithms like mergesort.

  function mergeSort(arr) {
    if (arr.length <= 1) {
      return arr;
    }
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);

    return merge(mergeSort(left), mergeSort(right));
  }

The mergeSort function divides the array into smaller arrays and sorts them. It then merges these smaller arrays back together, resulting in n log n time complexity.