Algorithms by the Numbers: Counting Steps, Growth Rates, Binary Search, Sorting Comparisons, Hash Table Load & Caching

What you'll build

What you will be able to do

Each lab ends with a concrete result that you build yourself and the checker confirms, cell by cell.

• Count the steps of a nested loop, of a loop that visits each pair once and of a loop that halves its range, and show that for 1,000 items almost all the work of a routine comes from its n² part.
• Fill a growth table from 10 to 1,000,000 items, measure how far n² runs away from n · log₂ n, compute 2ⁿ for small n and chart where it overtakes n².
• Compare the worst-case comparisons of linear and binary search from 20 to a billion items, then trace a binary search through a sorted list of 15 parcel numbers step by step.
• Count the comparisons of a simple sort and a merge-style sort up to a million items, then trace one pass of a neighbour-swapping sort on eight values and see the largest value travel to the end.
• Turn step counts into run times on a fictional test machine and work out the largest input each algorithm class can handle within a one-second budget.
• Calculate the load factor of four hash tables, estimate the probes per lookup with a simplified model, find how many items fit before a resize and size a table for next year as a power of two.
• Calculate the average access time of a cache in front of a slow database, compare six cache sizes, work out the hit rate needed for a target and pick the smallest cache size that reaches it.
• Count the copies a growing list makes with doubling and with fixed steps, then work out run times for three ways of finding duplicates and choose the one that fits both the time and the memory budget.