Big-O Notation: A Practical Guide for Coding Interviews

Big-O describes how an algorithm's runtime or memory grows as the input grows. It ignores constants and hardware, which is exactly what makes it useful: it lets you compare algorithms without running them.

The complexities that matter

• O(1) — constant time. Lookup in a hash map, indexing an array, push/pop on a stack.
• O(log n) — logarithmic. Binary search, balanced-tree operations. Halving the problem each step.
• O(n) — linear. A single pass over the input: linear search, summing an array.
• O(n log n) — linearithmic. Efficient sorting (merge sort, quicksort average case).
• O(n²) — quadratic. Nested loops: bubble sort, brute-force pair checks.
• O(2ⁿ) — exponential. Recursion that branches twice per call: naive Fibonacci.

How to read a loop nest

A loop that runs n times is O(n). Two independent loops run 2n times — still O(n), constants drop. A loop nested inside another, each to n, is O(n²). A loop that cuts the range in half each iteration is O(log n).

# O(n²): two nested loops
def has_pair_naive(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False

# O(n): one pass with a set
def has_pair(nums, target):
    seen = set()
    for x in nums:
        if target - x in seen:
            return True
        seen.add(x)
    return False

Amortized complexity

A dynamic array appends in O(1) on average, even though a resize occasionally copies everything. That occasional O(n) resize, spread across many O(1) appends, is called amortized O(1). It is the reason Python lists and C++ vectors stay fast.

The traps

• String concatenation in a loop is often O(n²) in languages with immutable strings — build a list and join instead.
• slicing or copying inside a loop can hide an O(n) inside what looks like an O(1) step.
• Recursion without memoization can quietly become exponential.

When in doubt, state the complexity out loud before you code. It signals you think in terms of scale — which is the whole point of the DSA arena.