Loading
Loading
Complexity Analysis
Where nested work comes from, and how to tell whether it can be removed.
By the end of this chapter
Every element is compared against every other element. The count is n(n-1)/2, which simplifies to n².
def closest_pair(nums): best = None for i in range(len(nums)): for j in range(i + 1, len(nums)): gap = abs(nums[i] - nums[j]) if best is None or gap < best: best = gap return bestAsk what the inner loop is actually computing. There are two common answers, and they have different fixes.
| What the inner loop does | Usual fix |
|---|---|
| Checks whether something exists | A hash set or map |
| Searches earlier elements for a complement | A hash map of what you have seen |
| Finds the next larger or smaller element | A monotonic stack |
| Recomputes a total over a range | A prefix sum |
| Compares against a sorted neighbour | Two pointers |
Sometimes the nesting is not removable. Comparing every pair to report all of them is inherently quadratic, because there are that many pairs to report.
Each element doubles the work, or each position multiplies the arrangements. This is the cost of exploring every subset or every ordering.
| n | 2ⁿ | n! |
|---|---|---|
| 10 | 1,024 | 3.6 million |
| 20 | 1 million | 2.4 × 10¹⁸ |
| 30 | 1 billion | unimaginable |
| Operation | Time | Space |
|---|---|---|
| Scan once | O(n) | O(1) |
| Scan with a setthe usual trade | O(n) | O(n) |
| Compare every pair | O(n²) | O(1) |
| Sort, then scan | O(n log n) | O(n) |
| Every subset | O(2ⁿ) | O(n) |
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: try 2 practice problems.