What is Big O notation?

AlgorithmsJunior~4 min read

Short answer

Big O is asymptotic notation that describes how an algorithm's running time or memory consumption grows depending on the input size n.
It ignores constants and lower-order terms, focusing on the dominant growth: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).
It is used to compare algorithms and assess scalability in time and memory (time/space complexity).

Big O (O-notation) describes an upper bound on the growth of a resource (usually time) of an algorithm as the input size n increases. It is a model: it abstracts away specific machines/languages and constant factors, showing how the algorithm scales.

Nearby notations: Θ (Theta) - a tight asymptotic bound, when the upper and lower bounds coincide; Ω (Omega) - a lower bound. In interviews, an O-estimate for the worst case is usually enough.

Why this is needed

To compare algorithms by scalability, not by specific milliseconds.
To choose data structures and approaches that will hold up under growing load.
To communicate decisions in a common language in team discussions and interviews.

Main complexity classes

Class	Description	Example
O(1)	Constant time/memory, does not depend on n	Array access by index
O(log n)	Logarithmic growth, halving the input	Binary search, operations on balanced trees
O(n)	Linear growth, a single pass	Summing an array, finding the minimum
O(n log n)	A linear pass × logarithmic depth	Merge sort, heap sort, efficient sorting algorithms
O(n²)	Quadratic growth, nested loops over n	Checking all pairs, simple sorts (bubble, insertion in the worst case)
O(2ⁿ)	Exponential growth, enumerating subsets	Full enumeration of all combinations, backtracking
O(n!)	Factorial growth	Permutations, a full enumeration of order

How to compute complexity: practical rules

Drop constants: O(3n + 10) → O(n), O(5) → O(1).
Take the dominant term: O(n + n²) → O(n²).
Sequential parts add up, nested ones multiply: a loop inside a loop over n → O(n²).
Divide-and-conquer often gives O(n log n) (for example, merge sort). Account for the recursion stack in memory.
Data structures matter: a hash table - average O(1), worst case O(n); a search tree - O(log n) when balanced, otherwise O(n).

Code examples (JavaScript)

javascript

// O(1) - constant complexity
function getFirst(arr) {
  return arr[0];
}

// O(n) - linear pass
function sum(arr) {
  let s = 0;
  for (const x of arr) s += x;
  return s;
}

// O(log n) - binary search (the array must be sorted)
function binarySearch(arr, target) {
  let l = 0, r = arr.length - 1;
  while (l <= r) {
    const m = l + ((r - l) >> 1);
    if (arr[m] === target) return m;
    if (arr[m] < target) l = m + 1; else r = m - 1;
  }
  return -1;
}

// O(n log n) - merge sort (average/worst), memory O(n)
function mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}
function merge(left, right) {
  const res = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) res.push(left[i++]); else res.push(right[j++]);
  }
  return res.concat(left.slice(i)).concat(right.slice(j));
}

// O(n^2) - naively checking for duplicates
function hasDuplicateNested(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// O(2^n) - generating all subsets (a power set)
function subsets(nums) {
  const res = [[]];
  for (const x of nums) {
    const add = res.map(s => s.concat(x));
    res.push(...add);
  }
  return res;
}

// Memory: O(1) vs O(n)
function maxValue(arr) { // O(1) extra memory
  let max = -Infinity;
  for (const x of arr) if (x > max) max = x;
  return max;
}
function copyArray(arr) { // O(n) extra memory
  const copy = [];
  for (const x of arr) copy.push(x);
  return copy;
}

// Amortized complexity: push on a dynamic array - O(1) amortized
class Stack {
  constructor() {
    this.data = new Array(1);
    this.size = 0;
  }
  push(x) {
    if (this.size === this.data.length) {
      const newData = new Array(this.data.length * 2);
      for (let i = 0; i < this.data.length; i++) newData[i] = this.data[i];
      this.data = newData; // a rare O(n) event
    }
    this.data[this.size++] = x; // O(1) usually, O(1) amortized
  }
  pop() {
    if (this.size === 0) return undefined;
    return this.data[--this.size];
  }
}

Time vs space complexity

Assess both resources: time and memory. Include in memory: extra structures (arrays, hash tables), the output result, the recursion stack, internal buffers. Sometimes it makes sense to trade memory for speed (a time-memory trade-off).

Worst, average, and best cases. Amortized estimate

Worst case: what is usually asked about in an interview - for example, a lookup in an unbalanced BST can be O(n).
Average case: useful for hash tables - lookup/insert is O(1) with a good hash function and low load.
Best case: rarely useful, but clarify it during analysis (for example, inserting into a sorted array for insertion sort is O(n) on average, O(n²) in the worst case, O(n) in the best case).
Amortized complexity: the average cost of an operation over a sequence - for example, dynamically resizing an array makes push O(1) amortized.

Typical mistakes and nuances

Ignoring hidden constants: O(n) with a huge constant can lose to O(n log n) for small n.
Forgetting to account for the cost of sorting: the bottleneck is often the sort itself, O(n log n).
Memory: the size of the output also counts (creating a new array is O(n)).
Hash tables: average O(1) is possible only with a good hash function and rebalancing (otherwise the worst case is O(n)).

How to answer in an interview

Denote n - the input size (and m, if there is a second parameter).
State the time and space complexity: "Time O(n log n), memory O(n) because of the temporary array".
Justify it using the rules: sequence/nesting/dominance. State the worst/average/best case, if relevant.
State your assumptions: "Hash operations are average O(1), I'm assuming a good hash function".
Compare alternatives briefly: "This approach is O(n log n), faster for large n, but requires O(n) memory, while the other one is O(1) memory but O(n²) in time".

Conclusion

Big O is the language for assessing the scalability of algorithms. By knowing the complexity classes, the rules for computing them, and typical data structures, you will be able to quickly justify your choice of solution and correctly estimate time and memory in an interview.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.