Counting steps

A computer does roughly 100 million simple steps per second. What matters is how the number of steps grows with the input size n.

One loop over n items: about n steps, written O(n). A loop inside a loop: about n × n, O(n²). Halving each time: about log₂ n, O(log n).