Analyzing Time & Space Complexity of Real Code

The complexity classes from the last chapter only become useful once you can look at an arbitrary piece of code and assign it one of those labels on sight. That is a pattern-recognition skill, and like any pattern-recognition skill, it comes from working through examples rather than memorizing definitions.

A single loop that visits every element once, doing a constant amount of work per element, is O(n) - regardless of what values happen to be in the list. Even a loop with an early return, like a search that stops the moment it finds a match, is still O(n) in the worst case, because a missing target or a match at the very last position forces every element to be checked.

When one loop is nested inside another and both depend on the same input size n, their costs multiply rather than add: n outer iterations, each running up to n inner iterations, gives roughly n times n, or n squared, total operations. This is the most common way ordinary-looking code quietly becomes O(n²), and it is exactly the shape that a set-based or hashmap-based rewrite (from the last chapter, and the hashing module ahead) is usually reached for to avoid.

A loop that shrinks the remaining problem by a constant fraction (usually half) on every iteration, rather than shrinking by one element at a time, takes O(log n) iterations to finish - dividing 1,000,000 in half repeatedly reaches 1 in only about 20 steps. Binary search, covered in full two modules from now, is built entirely on this pattern.

Space complexity asks a parallel question about memory instead of time: how much EXTRA memory does this function allocate, beyond the input it was given? A function that only ever uses a fixed handful of variables - a running total, a couple of index counters - is O(1) space, often called "in-place," because that extra memory does not grow no matter how large the input gets. A function that builds a brand-new list, dict, or set whose size scales with the input is O(n) space instead.

• -sum_all: O(n) time (one loop over the input), O(1) space (a single running total).
• -has_pair_with_sum: O(n²) time (nested loops over the same input), O(1) space (no extra structure grows with n).
• -reversed_copy vs reverse_in_place: identical O(n) time, but O(n) space against O(1) space - the space cost of a new list is easy to miss if only timing is measured.