Big-O and Complexity Analysis

1. What It Is and Why It Exists

Big-O notation describes how the running time (or memory) of an algorithm grows as the input size n grows, ignoring constant factors and lower-order terms. It answers the only scaling question an interviewer cares about: "If the input gets 10x bigger, what happens to your solution?" Without it you can only say "this feels fast" — which is useless when the difference between O(n) and O(n^2) is the difference between passing and timing out on n = 10^5.

The reason we drop constants and keep only the dominant term is that for large n, the highest-order term swamps everything else: 3n^2 + 1000n + 50000 is O(n^2) because once n is large the n^2 term decides the runtime, and hardware/language constants are not portable across machines. Big-O is an upper bound on growth rate, so it lets you compare algorithms by shape, not by stopwatch. Interviewers expect you to state complexity out loud while you code, not after.

2. Operations and Complexity

The "operations" here are the complexity classes you must recognize on sight, ordered from best to worst:

Rules interviewers probe: drop constants (O(2n) = O(n)), drop lower-order terms (O(n^2 + n) = O(n^2)), sequential code adds (O(n) + O(n) = O(n)), nested loops multiply (O(n) * O(m) = O(nm)). Distinguish best / average / worst case — interviewers almost always mean worst case unless you say otherwise; quicksort is the classic "average O(n log n), worst O(n^2)" trap. Space complexity counts extra memory you allocate (auxiliary), and recursion stack depth counts.

3. Implementation

There is nothing to implement; the skill is analyzing code. The reproducible technique: count how many times the innermost statement runs as a function of n.

Copy
# O(n): the loop body runs n times, each iteration is O(1).
def total(nums):
    s = 0
    for x in nums:        # n iterations
        s += x            # O(1) work
    return s              # -> O(n) time, O(1) extra space

# O(n^2): for each of n elements, an inner loop does up to n work.
def has_duplicate_pair(nums):
    for i in range(len(nums)):          # n
        for j in range(i + 1, len(nums)):  # ~n
            if nums[i] == nums[j]:      # O(1)
                return True
    return False                        # -> O(n^2) time, O(1) extra space

# O(log n): the search space halves every iteration.
def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                     # runs log2(n) times
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1                           # -> O(log n) time, O(1) extra space

# Recursion: solve T(n) by the recurrence. Master-theorem shortcut for
# T(n) = a*T(n/b) + f(n): merge sort is T(n) = 2T(n/2) + O(n) = O(n log n).
def merge_sort_cost(n):
    # 2 subcalls on n/2, plus O(n) merge -> O(n log n) total.
    pass

In an interview you do not "reach for a library" here — you narrate the analysis: count loop iterations, multiply nested loops, write the recurrence for recursion, and state the bound before the interviewer asks.

4. When to Reach for It

• Always, before you finish coding — state the time and space complexity of every solution unprompted.
• When the constraint says n <= 10^5 or larger → an O(n^2) solution will TLE; you need O(n log n) or better. (~10^8 simple operations/sec is the rule of thumb.)
• When n <= ~20 → exponential O(2^n) / O(n!) (bitmask, backtracking) is acceptable and often intended.
• When asked "can you do better?" → compare your current class to the next class down and identify what structure (hash, sort, two pointers) closes the gap.

5. Common Pitfalls

• Reporting best case as the answer. Saying "binary search is O(1) if we get lucky" — interviewers want worst case. Default to worst case.
• Ignoring hidden cost of built-ins. x in a_list is O(n), s = s + char in a loop is O(n^2) (string is immutable, rebuilt each time), slicing a[1:] is O(n). Misjudging these silently turns an O(n) analysis into O(n^2).
• Forgetting recursion stack space. A recursion n deep is O(n) auxiliary space even with no explicit data structure — say so.
• Multiplying when you should add. Two sequential loops are O(n), not O(n^2); a loop inside a loop is O(n^2). Misreading control flow is the most common error.
• Treating O(n log n) and O(n) as interchangeable. They differ enough to matter at scale; do not hand-wave the log n.

6. Interview Cheat Sheet

• "Big-O is the asymptotic upper bound on growth; I drop constants and lower-order terms and report worst case unless I say otherwise."
• "Sequential blocks add, nested loops multiply, and recursion is analyzed by its recurrence — merge sort's T(n) = 2T(n/2) + O(n) gives O(n log n)."
• "I read the constraints first: n <= 10^5 rules out O(n^2); n <= 20 invites an exponential search."
• "Space complexity is the auxiliary memory I allocate, and recursion depth counts toward it."

Follow-ups:

• "What's the difference between Big-O, Big-Θ, and Big-Ω?" — O is an upper bound, Ω a lower bound, Θ a tight bound (both). In interviews people say "O" but usually mean a tight worst-case bound.
• "Your solution is O(n^2). Can you do better?" — Identify the repeated work; replace a nested scan with a hash map (O(n)) or sort + two pointers (O(n log n)).
• "Is O(2n) worse than O(n)?" — No; constants are dropped, they are the same class. Different constants can matter in practice but not in Big-O.