How fast is a program?

Why does one app load instantly while another grinds forever? Often it's not your phone, but how cleverly the program computes. You already counted steps while searching and sorting. Now we turn that into a real superpower: you'll learn to predict how a program behaves as the data grows.

Steps instead of seconds

Measuring seconds is unfair: on a fast computer the same program runs quicker than on an old phone. That's why computer scientists prefer to count steps, for example comparisons. The number of steps is the same on every device. That way you can compare two methods without even running them.

How does the effort grow with n?

The exciting question is not how many steps a program needs for 10 entries, but what happens when 10 entries become 10000. We call the input size n. With linear search the step count grows directly with n: twice as many entries, twice as many steps. With binary search, each doubling of n adds only a single step, because every step halves the list. One condition matters: halving only works if the list is sorted.

Linear versus halving

For a list of 8 entries the difference is tiny: 8 steps versus 3 steps, who cares? But let n grow. At 1024 entries it's 1024 versus 10. At a million entries roughly a million versus 20. The halving method grows so slowly that even huge inputs barely matter. This growth behaviour is called logarithmic.

Why this decides everything

Search engines, map services, and streaming providers work with billions of entries. At such sizes, growth behaviour decides whether an answer arrives in milliseconds or only after hours. A faster computer helps a little, a better method helps enormously. That's why counting steps is one of the most important ideas in computer science.