Big-O & Complexity Analysis

Why complexity matters

Two correct programs can differ by a factor of a million in speed. Complexity analysis is how we predict that before running anything. In interviews it's also a language: when you say “this is O(n log n) time and O(n) space” you're telling the interviewer you understand why your code is fast.

We count how the number of basic operations grows as the input size n grows, ignoring constant factors and lower-order terms. We care about the growth rate because for large inputs, it dominates everything else.

The notation

In practice (and in interviews) people say “Big-O” when they mean the tight bound for the worst case. That's fine — just be precise when it matters, e.g. “quicksort is O(n log n) on average but O(n²) in the worst case.”

Rules for simplifying

1. Drop constants: O(3n + 5) → O(n).
2. Drop lower-order terms: O(n² + n log n + 100) → O(n²).
3. Different inputs get different variables: looping over array a then array b is O(a + b), not O(n). Nested loops over them are O(a·b).
4. Logs don't care about base: log₂ n and log₁₀ n differ by a constant factor, so we just write log n.

The common growth classes

Reading constraints to guess the solution

This is the most practical skill on this page. A typical judge runs roughly 10⁸ simple operations per second. So the input limits tell you which complexities are allowed:

Analyzing code

Sequential statements add

for x in arr:        # O(n)
    print(x)
for x in arr:        # O(n)
    for y in arr:    # O(n) each → O(n²)
        print(x, y)
# total: O(n + n²) = O(n²)

Nested loops multiply — but check the bounds

for i in range(n):
    for j in range(i + 1, n):   # runs n-1, n-2, ..., 0 times
        ...
# sum = n(n-1)/2 → still O(n²)

i = 1
while i < n:
    i *= 2          # i doubles: 1, 2, 4, ... → O(log n) iterations

for i in range(n):
    j = 1
    while j < n:
        j *= 2      # O(log n) per outer iteration → O(n log n) total

The “harmonic” loop

for i in range(1, n + 1):
    for j in range(i, n + 1, i):   # n/i iterations
        ...
# n/1 + n/2 + n/3 + ... + n/n = n · H(n) ≈ n ln n → O(n log n)

This shows up in sieves and divisor enumeration and surprises a lot of people.

Amortized analysis

Some operations are occasionally expensive but cheap on average over a sequence. The classic example is a dynamic array (Python list, C++ vector): when it fills, it doubles capacity and copies everything (O(n)), but that happens so rarely that n appends cost O(n) total → O(1) amortized per append.

Other amortized examples you'll meet:

• Monotonic stack: an inner while loop pops, but each element is pushed and popped at most once → O(n) total.
• Sliding window: the left pointer only moves forward → O(n) total even though there's a nested loop.
• Union-Find with path compression + union by rank: nearly O(1) per operation (inverse Ackermann).

Recursion complexity

For a recursive function, time = (number of calls) × (work per call). Draw the recursion tree.

def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)

Each call branches into 2, depth n → about 2ⁿ calls → O(2ⁿ). With memoization each n is computed once → O(n).

The Master Theorem (divide and conquer)

For recurrences of the form T(n) = a·T(n/b) + O(nᵈ):

Quick reference:

• Binary search: T(n) = T(n/2) + O(1) → O(log n)
• Merge sort: T(n) = 2T(n/2) + O(n) → O(n log n)
• Tree traversal: T(n) = 2T(n/2) + O(1) → O(n)

Space complexity

Count the extra memory your algorithm uses as a function of n:

• Variables and pointers: O(1)
• A new array/hash map of size n: O(n)
• A 2D DP table: O(n·m)
• Recursion stack: O(depth). A DFS on a skewed tree is O(n) stack space, a balanced one O(log n).

Best, average, worst case

Worked example: three solutions, three complexities

Problem: does an array contain any duplicate?

# O(n²) time, O(1) space — compare every pair
def has_dup_brute(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

# O(n log n) time, O(1) extra (in-place sort) — duplicates become adjacent
def has_dup_sort(nums):
    nums.sort()
    return any(nums[i] == nums[i - 1] for i in range(1, len(nums)))

# O(n) time, O(n) space — trade memory for speed
def has_dup_hash(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

// O(n) expected time, O(n) space
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.count(x)) return true;
        seen.insert(x);
    }
    return false;
}

This time–space trade-off (spend memory on a hash set or table to save time) is the single most common optimization in interview problems.

Hidden costs to watch for

• String concatenation in a loop in Python/Java creates a new string each time → O(n²). Use a list and ''.join() / StringBuilder.
• Slicing arr[1:] copies → O(n) per call. Recursion that slices is often secretly O(n²). Pass indices instead.
• x in list is O(n); x in set is O(1) average.
• list.pop(0) and list.insert(0, x) are O(n). Use collections.deque.
• Sorting inside a loop multiplies by O(n log n).
• C++ map/set are O(log n) balanced trees; unordered_map is O(1) average.

Summary

• Big-O = growth rate; drop constants and lower-order terms.
• Read the constraints first — they tell you the target complexity.
• Nested loops multiply only if the inner loop restarts; pointers that only move forward are amortized O(n).
• Recursion: calls × work per call; divide & conquer: Master Theorem.
• Always state both time and space, and mention the recursion stack.