CATEGORY 0 OF 13

Big O & Complexity

Understand how to measure algorithm efficiency with Big O notation — the single most important concept for technical interviews.

Time: Varies

Space: Varies

Learn & Reference

Understanding the Pattern

Big O & Complexity

Big O notation is the universal language for describing how an algorithm's performance scales as input grows. Every technical interview expects you to analyze your solution's time and space complexity. Master this first — it's the lens through which every other pattern makes sense.

What Is Big O?

Big O describes the growth rate of an algorithm relative to input size n. It answers: "If I double the input, how much more work does the algorithm do?"

Key principles:

We measure growth, not exact time — O(n) doesn't mean "n milliseconds," it means "time grows linearly with input"
Drop constants — O(2n) simplifies to O(n). Constants don't matter at scale
Drop lower-order terms — O(n² + n) simplifies to O(n²). The dominant term wins
We usually analyze worst-case — unless stated otherwise, Big O means the worst input scenario

The Complexity Hierarchy

From fastest to slowest, memorize these growth rates:

Big O        Name           Example                   n=1,000        n=1,000,000
─────        ────           ───────                   ───────        ───────────
O(1)         Constant       Array access, hash lookup 1 op           1 op
O(log n)     Logarithmic    Binary search             ~10 ops        ~20 ops
O(n)         Linear         Single loop, linear scan  1,000 ops      1,000,000 ops
O(n log n)   Linearithmic   Merge sort, heap sort     ~10,000 ops    ~20,000,000 ops
O(n²)        Quadratic      Nested loops, bubble sort 1,000,000 ops  1,000,000,000,000 ops
O(2ⁿ)        Exponential    All subsets, recursive fib  impossible     impossible
O(n!)        Factorial      All permutations            impossible     impossible

The cliff between O(n log n) and O(n²) is where most interview problems live. An O(n²) solution on 100,000 elements takes 10 billion operations — far too slow. An O(n) or O(n log n) solution handles it instantly.

How to Analyze Code

Rule 1: Simple Loops = O(n)

1for i in range(n):       # O(n) — runs n times
2    do_something()       # O(1) per iteration
3# Total: O(n)

Rule 2: Nested Loops Multiply

1for i in range(n):       # O(n)
2    for j in range(n):   # O(n) per iteration of outer loop
3        do_something()   # O(1)
4# Total: O(n) * O(n) = O(n²)

Rule 3: Sequential Blocks Add (Then Simplify)

1for i in range(n):       # O(n)
2    do_something()
3
4for i in range(n):       # O(n)
5    for j in range(n):   # O(n)
6        do_something()
7# Total: O(n) + O(n²) = O(n²)  (drop lower term)

Rule 4: Halving = O(log n)

1while n > 0:
2    n = n // 2           # Halves each time
3# Total: O(log n) — only ~20 iterations for n = 1,000,000

Rule 5: Watch Hidden Loops

Built-in methods can hide O(n) work:

list.sort() is O(n log n)
x in list is O(n) (linear scan)
list.index(x) is O(n)
string + string in a loop is O(n) per concatenation (creates new string)
x in set is O(1) (hash lookup — this is fast!)

Space Complexity

Space complexity measures extra memory your algorithm uses beyond the input.

Input doesn't count — if you receive an array of size n, that's not your space
O(1) space means you only use a fixed number of variables (like counters or pointers)
O(n) space means you create a data structure proportional to input (like a hash map or copy of the array)
Recursion uses O(depth) space for the call stack — often overlooked!

1# O(1) space — just two variables
2def find_max(arr):
3    max_val = arr[0]
4    for x in arr:
5        max_val = max(max_val, x)
6    return max_val
7
8# O(n) space — creates a set
9def has_duplicate(arr):
10    seen = set()
11    for x in arr:
12        if x in seen:
13            return True
14        seen.add(x)
15    return False

Why It Matters in Interviews

Most interview problems have constraints like 1 <= n <= 10⁵. This is a hint about the expected complexity:

Constraint      Expected Complexity    Reasoning
──────────      ───────────────────    ─────────
n <= 10         O(n!) or O(2ⁿ)        Backtracking / brute force OK
n <= 1,000      O(n²)                  Nested loops acceptable
n <= 100,000    O(n log n) or O(n)     Must use efficient pattern
n <= 1,000,000  O(n) or O(log n)       Linear or better required

When an interviewer says "Can you do better?", they're asking you to reduce the Big O.

Common Mistakes

Confusing best, average, and worst case: Big O typically describes worst-case. An O(n) algorithm doesn't always take n steps — but it never takes more than cn steps for some constant c
Forgetting hidden loops in built-in methods: x in list looks like O(1) but is actually O(n). Use a set or hash map for O(1) lookups
Not counting recursion stack space: A recursive function with depth n uses O(n) space even if it creates no data structures
Assuming O(n log n) is always better than O(n²): For small inputs (n < 50), constants matter more than growth rate. But interviews care about large inputs
String concatenation in loops: Building a string with += in a loop is O(n²) total in many languages — use a list/array and join at the end

When to Use

An interview problem specifies input size constraints (n <= 10⁵ means O(n²) is too slow)

An interviewer asks Can you do better? or What's the time complexity?

You need to choose between multiple approaches (sort first vs hash map vs brute force)

Your solution uses nested loops — can you eliminate the inner loop?

You're creating extra data structures — is the space trade-off worth the time improvement?

A problem asks you to find/search/check something — O(1) lookup with hash maps vs O(n) scan

Template

1# --- Analyze Your Approach ---
2# Before coding, identify the complexity:
3#
4# 1. Count nested loops over input:
5#    - 1 loop = O(n), 2 nested = O(n²)
6#
7# 2. Check for hidden O(n) operations:
8#    - "x in list" is O(n) → use a set instead
9#
10# 3. Consider the trade-off:
11#    - More space (hash map) = less time
12#    - O(n) time + O(n) space often beats O(n²) time + O(1) space
13
14# Template: O(n) single-pass with hash map
15def solve(arr):
16    seen = {}           # O(n) space
17    for x in arr:       # O(n) time
18        complement = target - x
19        if complement in seen:   # O(1) lookup
20            return [seen[complement], x]
21        seen[x] = x
22    return []

{ }

Syntax Reference

1# === Array / List Operations ===
2arr[i]                    # O(1) — direct index access
3arr.append(x)             # O(1) amortized — add to end
4arr.pop()                 # O(1) — remove from end
5arr.pop(0)                # O(n) — remove from front (shifts all)
6arr.insert(i, x)          # O(n) — shifts elements right
7x in arr                  # O(n) — linear scan!
8arr.index(x)              # O(n) — linear search
9arr.sort()                # O(n log n) — Timsort
10sorted(arr)               # O(n log n) — returns new list
11len(arr)                  # O(1) — stored property
12
13# === Dict / Hash Map ===
14d[key]                    # O(1) average — hash lookup
15d[key] = val              # O(1) average — hash insert
16key in d                  # O(1) average — hash check
17del d[key]                # O(1) average — hash delete
18d.keys() / d.values()     # O(n) — creates view
19
20# === Set ===
21s.add(x)                  # O(1) average
22x in s                    # O(1) average — THIS IS FAST!
23s.remove(x)               # O(1) average
24s & t                     # O(min(n,m)) — intersection
25
26# === String ===
27s[i]                      # O(1) — char access
28s + t                     # O(n+m) — creates NEW string
29s * k                     # O(n*k) — repeats
30''.join(list)             # O(n) — efficient concatenation
31s.split()                 # O(n)
32s.find(sub)               # O(n*m) — substring search

📋

Common Recipes

1# --- O(1) — Constant Time ---
2def get_first(arr):
3    """Array access and hash lookup are O(1)"""
4    return arr[0]       # Direct index: always instant
5
6# --- O(n) — Linear Time ---
7def find_max(arr):
8    """Single pass through array"""
9    result = arr[0]
10    for x in arr:       # One loop = O(n)
11        result = max(result, x)
12    return result
13
14# --- O(n²) — Quadratic Time (AVOID for large n) ---
15def has_pair_sum_slow(arr, target):
16    """Brute force: check every pair"""
17    for i in range(len(arr)):           # O(n)
18        for j in range(i+1, len(arr)):  # O(n) per outer
19            if arr[i] + arr[j] == target:
20                return True
21    return False
22# Total: O(n²) — TLEs on n > 10,000
23
24# --- O(n) — Same problem, optimal ---
25def has_pair_sum_fast(arr, target):
26    """Hash set for O(1) lookups"""
27    seen = set()
28    for x in arr:                   # O(n)
29        if target - x in seen:      # O(1) lookup!
30            return True
31        seen.add(x)                 # O(1) insert
32    return False
33# Total: O(n) — handles n = 1,000,000 easily

O(n)

Complexity

Data Structure	Access	Search	Insert	Delete
Array / List	O(1)	O(n)	O(n)*	O(n)*
Hash Map / Dict	O(1)	O(1)	O(1)	O(1)
Hash Set	—	O(1)	O(1)	O(1)
Stack (array)	O(n)	O(n)	O(1)†	O(1)†
Queue (linked)	O(n)	O(n)	O(1)	O(1)
Sorted Array	O(1)	O(log n)	O(n)	O(n)
Binary Heap	O(1)‡	O(n)	O(log n)	O(log n)
Binary Search Tree	O(log n)	O(log n)	O(log n)	O(log n)

Watch Out

✗Confusing best, average, and worst case: Big O typically describes worst-case. An O(n) algorithm doesn't always take n steps — but it never takes more than cn steps for some constant c
✗Forgetting hidden loops in built-in methods: `x in list` looks like O(1) but is actually O(n). Use a set or hash map for O(1) lookups
✗Not counting recursion stack space: A recursive function with depth n uses O(n) space even if it creates no data structures
✗Assuming O(n log n) is always better than O(n²): For small inputs (n < 50), constants matter more than growth rate. But interviews care about large inputs
✗String concatenation in loops: Building a string with `+=` in a loop is O(n²) total in many languages — use a list/array and join at the end

PRACTICE PROBLEMS

String Manipulation