Card 08/ 08
Recap: Analysing Complexity
Count the runs, multiply nested counts, add the frames, and look inside every built-in call.
Analysing Complexity comes down to the six ideas below, each listed with the card that covers it.
| The idea | Where |
|---|---|
| Count how often each line runs in terms of n, then keep the largest term | Counting the Work a Function Does |
| Loops in sequence add, nested loops multiply, and a counter that halves gives log n | Analyse Sequential and Nested Loops |
| Multiply by how often the inner loop runs, which is not always n | Calling Every Pair of Nested Loops O(n²) |
| Extra space counts what a function adds, with one frame for every call still waiting | Space Complexity and the Call Stack |
| Independent inputs keep a variable each: O(n · m), not O(n²) | Complexity Example: Comparing Two Lists of Different Lengths |
| Searching a list, slicing it or building a string in a loop is linear work | A Linear Cost Hidden Inside a Built-In Call |
Together they let you read a function's time and space from its code, and find the line that makes it slower than it looks.
← → move through sections and cards