Free lessonsComplexity · Stage 0 · Counting work · Step 1

One loop, counted

Work out how many times a loop runs, without running it. About 7 minutes.

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

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

Quick check

i starts at 0 and jumps by 5 while i < 10. How many passes does the loop make?

Show the answer

2. i = 0 and i = 5 pass. Then i = 10 is not less than 10. 10 // 5 = 2 with no leftover.

Your problem

Count the passes

This loop runs a body while i < n: i starts at 0 and grows by step after every pass. Return how many times the body runs. n can be two billion, so count the passes instead of making them.

Example

n = 10, step = 3 → 4

0 ≤ n ≤ 2,000,000,000 · 1 ≤ step ≤ 1,000,000,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.

Start coding