Practise Big-O by Measuring Real Code

A practical approach

Step 1

Write small functions with known complexity, such as summing a list, sorting it and checking all pairs for duplicates.

Step 2

Time each function for input sizes like 1,000, 2,000, 4,000 and 8,000, repeating each measurement a few times.

Step 3

Observe how time changes when input doubles: roughly double for O(n), slightly more than double for O(n log n) and about four times for O(n squared).

Step 4

Rewrite the pair-checking function using a set and measure again to see the improvement.

Step 5

Look through your own projects for nested loops over the same collection and estimate their complexity.

Worked example

A learner times a function that finds duplicate emails by comparing every pair. At 2,000 emails it takes a fraction of a second; at 16,000 it takes dozens of times longer, matching the quadratic pattern. Rewriting it to track seen emails in a set makes the run time grow almost linearly, which explains why the original version slowed a registration import so badly.

A mistake to avoid

Do not rely on a single measurement or very small inputs. Timing noise, caching and start-up costs dominate small runs. Measure several sizes and repeat runs before drawing conclusions.

Try it yourself

Implement the three functions above in a language you use, measure them at four input sizes and plot or tabulate the results. Write one sentence for each explaining how the numbers reflect its Big-O.

Your implementation checklist

• I can predict how O(n), O(n log n) and O(n squared) grow when input doubles
• I measure several input sizes with repeated runs
• I can rewrite a quadratic search using a hash-based structure
• I spot nested loops over the same data in real code
• I connect measurements to complexity in plain language