How to say whether code is fast

You are not measuring seconds. Seconds depend on your laptop, on what else is running, and on the weather inside the processor. Big-O describes the shape of the growth, which is the part that stays true everywhere.

The handful you actually need, from best to worst. O(1): constant — the same time no matter how much data, like fetching item number 500 from a list. O(log n): grows extremely slowly, because each step throws away half of what is left; going from a thousand items to a million adds only about ten steps. O(n): grows in step with the data — reading every item once. O(n log n): the realistic best for sorting things. O(n²): a loop inside a loop, where ten times the data means about a hundred times the work.

The reason this matters is that the difference is not academic. Something O(n²) that takes one second on 1,000 records takes about three hours on 100,000. That is the shape of a dashboard which worked fine at launch and fell over the day the customer table grew.

There are two related notations you will see. Big-Omega describes a lower bound — the best case. Big-Theta describes a tight bound, used when best and worst are the same shape. In practice people say Big-O and mean the worst case, and that convention is fine to adopt.

One caveat worth holding onto: Big-O ignores constant factors, so an O(n) method can lose to an O(n²) one on small inputs. It describes what happens as things get large, not what is fastest on ten items.

You met the idea in week 12. Now look at the machinery. Every time a function is called, the computer sets aside a small area holding that call's own variables. That area is a stack frame, and the pile of them is the call stack.

Frames are only released when a call finishes. So a recursive function that goes 10,000 deep has 10,000 frames alive at once, each using real memory. That is why recursion depth is not free, and why Python stops you at around a thousand deep rather than letting the program consume all available memory.

The reason recursion earns its place is that some structures are themselves recursive. A folder contains folders. A tree node's children are themselves trees. Writing a loop to walk those means manually keeping track of where you are; recursion lets the call stack do that bookkeeping for you, and the code ends up shorter and closer to the shape of the problem.

Any recursive function can be rewritten as a loop with an explicit stack, and sometimes should be, when the depth would otherwise be too great. It is useful to know the two are equivalent, because it means recursion is a convenience rather than a special power.

Logarithms sound intimidating and are simple in this context: the logarithm of a number is roughly how many times you can halve it before reaching one. A million halves down to one in about twenty steps. That single fact is the entire reason binary search and balanced trees are fast, so it is worth having properly rather than approximately.

Modular arithmetic is the remainder operator you already met, taken seriously. It is clock arithmetic — after 12 comes 1 again. Hash tables use it to fold any number down into a valid slot position, which is what makes dictionaries work.

Prime numbers and greatest common divisors underpin cryptography. You need only a working familiarity here, not depth.

Basic combinatorics — how many ways there are to arrange or choose things — helps you sanity-check whether a brute-force approach is even possible. If a problem has 2 to the power 50 possible arrangements, no amount of clever coding will let you try them all, and knowing that early saves you an afternoon.