Recap — Reading Time and Space Complexity

# Reading Time and Space Complexity Every coding interview opens with "What's the time complexity?" Knowing how to answer fast — and correctly — is the floor for getting hired. ## The Big-O ladder ``` O(1) constant — hashmap lookup, array index O(log N) logarithmic — binary search O(N) linear — single loop over input O(N log N) linearithmic — efficient sort (merge, quick, heap) O(N²) quadratic — nested loops over input O(2ᴺ) exponential — recursive subset/permutation generation O(N!) factorial — generating all permutations ``` For N = 1000: - O(N) ≈ 1,000 ops - O(N log N) ≈ 10,000 ops - O(N²) ≈ 1,000,000 ops - O(2ᴺ) ≈ a number larger than atoms in the universe In an interview at N = 10⁵, your solution should be O(N log N) or better. At N = 10⁴, O(N²) might pass. At N = 20-30 input size, O(2ᴺ) is fine for subset problems. ## Reading complexity from code ### Single loop → O(N) ```python for x in arr: # N iterations process(x) # O(1) work # Total: O(N) ``` ### Nested loops → O(N²) ```python for i in arr: # N iterations for j in arr: # N iterations each compare(i, j) # Total: O(N²) ``` ### Loop with halving → O(log N) ```python n = len(arr) while n > 0: process() n //= 2 # halve each step # Total: O(log N) ``` ### Loop calling a O(log N) operation → O(N log N) ```python for x in arr: # N iterations binary_search(sorted_arr, x) # O(log N) each # Total: O(N log N) ``` ### Recursion with two recursive calls → check the tree depth ```python def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) # tree branches 2x at each level, depth N # Total: O(2ᴺ) ``` With memoization, the same problem becomes O(N). ## Space complexity Stack space counts. A recursive function that calls itself N times deep uses O(N) stack space — even if no explicit data structures are allocated. ```python def sum_list(arr): if not arr: return 0 return arr[0] + sum_list(arr[1:]) # O(N) stack + O(N) for the slices ``` The iterative version is O(1) space: ```python def sum_list(arr): total = 0 for x in arr: # O(1) extra space total += x return total ``` ## Best, average, worst case Quicksort: - Best: O(N log N) - Average: O(N log N) - Worst: O(N²) (already-sorted input with naive pivot) Hashmap operations: - Average: O(1) - Worst: O(N) (hash collisions) In interviews, "what's the complexity?" usually means worst case unless specified. ## The amortized concept Some operations are sometimes expensive but cheap on average. Example: Python list `.append()`: - Usually O(1). - Sometimes O(N) when the underlying array doubles. - Amortized: O(1) — the cost averages out across many appends. ## Common mistakes 1. **Counting work inside a constant-time helper.** `process(x)` is O(1); doesn't add to outer complexity. 2. **Ignoring slicing cost in Python.** `arr[1:]` creates a copy — O(N) extra work. 3. **Forgetting hidden O(N) operations.** `x in list` is O(N); `x in set` is O(1). 4. **Confusing N and log N.** A loop that halves runs log₂N times, not N. 5. **Ignoring stack space.** Deep recursion = O(N) space even with no explicit data structure. ## Interview script When asked "what's the complexity?": 1. Identify the input(s): "N is the length of the array." 2. Walk through the dominant work: "I loop through the array once → O(N), then for each element I do a constant-time lookup → still O(N) total." 3. Space: "I use a set of N elements → O(N) space." 4. Mention trade-offs: "We could do it in O(N²) time and O(1) space by checking pairs, but the hashmap approach is faster." Sound like a systems thinker, not just a coder. ## Takeaway Big-O ladder: O(1), log N, N, N log N, N², 2ᴺ. Read code top-down: single loop = N, nested = N², halving = log N. Watch out for hidden O(N) operations (Python slicing, `in list`). Count stack space for recursion. Always answer complexity questions explicitly — interviewers want to hear you reason about it.