Exit
  1. Learn
  2. Check
  3. Solve
  4. Reflect

Speed is counted, not timed

Ask two friends how fast they can sort a pile of letters and one will say "five minutes", but on a different day or with a different pile that changes. Computers differ in the same way, so we don't measure code in seconds. We count how many times the busiest line runs.

A loop that visits each of n values runs n times, so its work grows in step with n.

n passes: for a loop over n values. We call this O(n), linear time.
n = 10, step = 3
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
i

i = 0 < 10: pass 1.

Move 1 of 4

Jumps of any size

Now suppose the loop jumps ahead by a fixed step instead of by 1, like climbing stairs two at a time. You don't have to run it to know how many passes it makes: just count the jumps.

Full jumps fit n divided by the step, rounded down, and if a leftover bit remains, that needs one more pass.

Full jumps: n divided by the step, rounded down.
A leftover: when the division isn't exact, adds one more pass.
In code
runs = n // step
if n % step != 0:
    runs += 1
return runs