Big-O Notation & Complexity Analysis

0/12 in this phase0/57 across the roadmap

📖 Concept

Big-O notation describes how the runtime or space usage of an algorithm grows relative to the input size. It's the universal language for comparing algorithm efficiency.

Why it matters: Every technical interview asks about complexity. Every production decision about which algorithm or data structure to use depends on Big-O. Without it, you can't reason about whether your code will handle 1 million users.

The key idea: Big-O measures the worst-case growth rate, dropping constants and lower-order terms:

O(1) — Constant — Same time regardless of input size (hash map lookup)
O(log n) — Logarithmic — Halving the problem each step (binary search)
O(n) — Linear — Visit each element once (array scan)
O(n log n) — Linearithmic — Efficient sorting (merge sort, quick sort)
O(n²) — Quadratic — Nested loops (bubble sort, brute force pairs)
O(2ⁿ) — Exponential — Doubling at each step (recursive fibonacci)
O(n!) — Factorial — All permutations (traveling salesman brute force)

Visual intuition:

Input size:     10      100       1,000      1,000,000
O(1):           1       1         1          1
O(log n):       3       7         10         20
O(n):           10      100       1,000      1,000,000
O(n log n):     30      700       10,000     20,000,000
O(n²):          100     10,000    1,000,000  1,000,000,000,000 💀

How to calculate Big-O:

Count the number of operations as a function of n
Drop constants: O(3n) → O(n)
Drop lower-order terms: O(n² + n) → O(n²)
Focus on the dominant term as n → infinity

🏠 Real-world analogy: If you lose your keys in the house, O(1) is knowing they're on the hook. O(n) is checking each room one by one. O(n²) is checking each room AND every drawer in every room for each attempt.

💻 Code Example

codeTap to expand ⛶

1// O(1) — Constant time
2function getFirst(arr) {
3  return arr[0]; // Always one operation, regardless of array size
4}
5
6// O(log n) — Logarithmic (binary search)
7function binarySearch(arr, target) {
8  let left = 0, right = arr.length - 1;
9  while (left <= right) {
10    const mid = Math.floor((left + right) / 2);
11    if (arr[mid] === target) return mid;
12    if (arr[mid] < target) left = mid + 1;
13    else right = mid - 1;
14  }
15  return -1; // Halves search space each iteration
16}
17
18// O(n) — Linear
19function findMax(arr) {
20  let max = arr[0];
21  for (let i = 1; i < arr.length; i++) { // Visits each element once
22    if (arr[i] > max) max = arr[i];
23  }
24  return max;
25}
26
27// O(n²) — Quadratic
28function hasDuplicate(arr) {
29  for (let i = 0; i < arr.length; i++) {       // n iterations
30    for (let j = i + 1; j < arr.length; j++) {  // n iterations (nested)
31      if (arr[i] === arr[j]) return true;
32    }
33  }
34  return false;
35}
36
37// O(2ⁿ) — Exponential (naive fibonacci)
38function fib(n) {
39  if (n <= 1) return n;
40  return fib(n - 1) + fib(n - 2); // Two recursive calls per level
41}
42
43// TypeScript version with types
44function binarySearchTS(arr: number[], target: number): number {
45  let left: number = 0, right: number = arr.length - 1;
46  while (left <= right) {
47    const mid: number = Math.floor((left + right) / 2);
48    if (arr[mid] === target) return mid;
49    if (arr[mid] < target) left = mid + 1;
50    else right = mid - 1;
51  }
52  return -1;
53}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

What is the Big-O of accessing an element in an array by index?
Determine Big-O: a loop from 0 to n that increments by 2 each time
Determine Big-O: two nested loops, outer 0→n, inner 0→n
Determine Big-O: a loop from n down to 1, halving each time
Analyze: for (i=0; i<n; i++) { for (j=0; j<100; j++) { ... } }
What's the complexity of: for(i=1; i<n; i*=2) { for(j=0; j<n; j++) {} }
Rank these from fastest to slowest: O(n!), O(2ⁿ), O(n²), O(n log n), O(n), O(log n), O(1)
A function calls itself twice with n-1. What's the time complexity?
You have O(n) + O(n²) + O(n³). What's the overall Big-O?
Prove that O(100n + 50) simplifies to O(n).

Debugging Exercise: This function claims to be O(n) — is it? Find the hidden complexity:

function mystery(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    result.unshift(arr[i]); // ← unshift is O(n)! Total: O(n²)
  }
  return result;
}

⚠️ Common Mistakes

Forgetting that Big-O drops constants — O(2n) is O(n), not O(2n)
Confusing O(log n) base — in Big-O, all logarithmic bases are equivalent because log_a(n) = log_b(n) / log_b(a), and 1/log_b(a) is a constant
Not recognizing hidden O(n) operations — array.unshift(), array.splice(), string concatenation in loops are all O(n)
Thinking O(n + m) simplifies to O(n) — if m is independent of n, you must keep both
Assuming hash map operations are always O(1) — they're O(1) amortized but O(n) worst case with collisions

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Big-O Notation & Complexity Analysis

Was this topic helpful?

Next →Time Complexity vs Space Complexity