Counting Operations to Compare Algorithms
Working out how many comparisons or swaps a method performs on an input of a given size, and writing that count as a formula in n. Two algorithms can then be compared without running either one.
What a learner can do afterwards
- Count the comparisons a search makes on the same list of 64 by two different methods
- Write the operation count of a loop as a formula in the input size n
- Explain why a timed run on one laptop is weaker evidence than a count
1 · Read
Two ways to find a name in a class list can both give the right answer while one does far more work. Counting the operations each method performs gives a fair count beyond one laptop. Call the input size n: the number of items the algorithm must handle, such as the length of the list being searched.
Take a list of 64 items. Linear search checks one item after another and can need all 64 comparisons in the worst case. Binary search halves the sorted list, throwing away the half that cannot hold the target, and needs only about 6 or 7 guesses. Worst case counts the most steps over all inputs of size n, so the promise holds every time.
Write a loop cost as a formula in n: count the work per pass and multiply by the number of passes. A loop doing 3 steps per item plus setup costs 3n + 7. Doubling shows the shape: doubling the list doubles linear work, while halving needs about one extra guess.
A timed run on one laptop is weak evidence. The time depends on machine, language and background load, while an operation count describes the algorithm itself. Build the habit this topic needs: count before you time, then ask which count grows more slowly as the list gets longer.
Count the operations first, and the fair comparison follows.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.