Suggest an edit

Improve this article

Refine the answer for “What is Big O notation?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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).

## Detailed breakdown

### What Big O is

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

1. Drop constants: O(3n + 10) → O(n), O(5) → O(1).
2. Take the dominant term: O(n + n²) → O(n²).
3. Sequential parts add up, nested ones multiply: a loop inside a loop over n → O(n²).
4. Divide-and-conquer often gives O(n log n) (for example, merge sort). Account for the recursion stack in memory.
5. 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

1. Denote n - the input size (and m, if there is a second parameter).
2. State the time and space complexity: "Time O(n log n), memory O(n) because of the temporary array".
3. Justify it using the rules: sequence/nesting/dominance. State the worst/average/best case, if relevant.
4. State your assumptions: "Hash operations are average O(1), I'm assuming a good hash function".
5. 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.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts1149 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.