What is the 'big O' notation?

Big O notation describes the upper bound of an algorithm's complexity — how quickly the execution time or memory usage increases depending on the size of the input data. It is used to compare the efficiency of algorithms.

Main types of complexity according to Big O notation:

Notation	Description	Example
O(1)	Constant time	Accessing an array element by index
O(log n)	Logarithmic time	Binary search
O(n)	Linear time	Searching for an element in an unsorted list
O(n log n)	Linear-logarithmic	Quick sort (average case)
O(n²)	Quadratic time	Bubble sort
O(2ⁿ)	Exponential time	Solving the Traveling Salesman Problem by brute force

Example of complexity analysis:

// Example O(1)
function getFirstElement(arr) {
  return arr[0]; // Access by index takes constant time regardless of array size
}

// Example O(n)
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) { // Loop runs n times, where n is the array length
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

// Example O(n^2)
function multiplyMatrices(matrixA, matrixB) {
  const n = matrixA.length;
  const result = [];
  for (let i = 0; i < n; i++) { // First loop (n iterations)
    result[i] = [];
    for (let j = 0; j < n; j++) { // Second loop (n iterations)
      let sum = 0;
      for (let k = 0; k < n; k++) { // Third loop (n iterations)
        sum += matrixA[i][k] * matrixB[k][j];
      }
      result[i][j] = sum;
    }
  }
  return result;
}

Big O notation allows us to abstract from specific machines and constant factors, focusing on how the complexity grows with increasing data size. This helps in choosing the most suitable algorithm for solving a problem, especially when working with large volumes of data.