Repeating Work: Loops and a Step Counter

3.1Decisions first

Before repetition, one small tool: doing something only in certain cases. Python checks the condition, and runs the indented block only if it is true.

temperature = 31

if temperature > 30:
    print("Hot")
elif temperature > 15:
    print("Pleasant")
else:
    print("Cold")

Two things trip up beginners: the colon at the end of the line, and the indentation (four spaces). In Python the indentation is not decoration — it is how the language knows which lines belong to the if.

The order matters. Python checks the branches top to bottom and takes the first one that is true, then skips the rest. That is why the "Pleasant" branch can safely say just > 15: if the temperature had been above 30 we would already have stopped at "Hot". Read a chain of elifs as "otherwise, if…".

3.2The for loop: do this n times

for i in range(5):
    print("step", i)

range(5) produces 0, 1, 2, 3, 4 — five values, starting at zero, stopping before five. Programmers count from zero often enough that you will stop noticing within a fortnight.

• range(5) → 0 1 2 3 4
• range(1, 6) → 1 2 3 4 5
• range(0, 10, 2) → 0 2 4 6 8 (step of two)

Adding up the numbers from 1 to n is the classic first loop:

n = 100
total = 0

for number in range(1, n + 1):
    total = total + number

print(f"The numbers 1 to {n} add up to {total}")

The pattern — start an accumulator at zero, add to it inside the loop, use it after — is worth memorising. You will write it a hundred times.

3.3The while loop: keep going until

Use for when you know how many repetitions you need, while when you do not.

remaining = 1000
reductions = 0

while remaining > 1:
    remaining = remaining // 2   # halve the size, rounding down
    reductions = reductions + 1

print(f"Size left: {remaining}, reductions: {reductions}")

This captures the repeated-halving idea from week 1, but counts integer size reductions, not a complete search. The sizes are 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1: nine reductions. Change 1000 to 1 000 000 and the count is 19. The loop does not inspect a target or count a final candidate comparison, so do not equate these exact counts with the guessing game.

3.4Counting the work

Here is the technique that carries the whole course. Add a variable whose only job is to count how many times the interesting line runs.

n = 50
steps = 0
total = 0

for number in range(1, n + 1):
    total = total + number
    steps = steps + 1          # one unit of work

print(f"n = {n}, result = {total}, steps = {steps}")

Run it with n = 50, then 100, then 200. The step count is always exactly n. Double the input, double the work: a straight-line relationship. In week 8 this gets the name O(n), but you can already see it in your own output.

3.5A loop inside a loop

Now the moment that makes people sit up. Put one loop inside another:

n = 5
steps = 0

for i in range(n):
    for j in range(n):
        steps = steps + 1

print(f"n = {n}, steps = {steps}")

The inner loop runs n times for each pass of the outer loop, so the total is n × n. Fill in this table by running the code — do not guess:

Ten times more input, a hundred times more work. This is why "it worked fine on my test data" and "it froze on the real data" are the same program. Nested loops are not forbidden — sometimes you genuinely must compare every pair — but from now on, when you write one, you should feel a small alarm go off.

3.6Deciding inside a loop: break and continue

Combining a decision with a loop is where loops earn their keep. Two keywords give you fine control: break leaves the loop immediately, and continue skips the rest of the current pass and moves on to the next.

Early exit with break. Suppose we want the first number whose square is over 1000, and we want to know how many we had to check:

steps = 0
answer = None

for k in range(1, 1000):
    steps = steps + 1
    if k * k > 1000:
        answer = k
        break              # found it — no need to look further

print(f"first is {answer}, checked {steps} numbers")

Without break the loop would grind on to 999 for no reason. Stopping early is exactly what makes a "best case" cheaper than a "worst case" — a distinction we make precise when we search lists in week 4.

Skipping with continue. Add up only the numbers from 1 to 20 that are not multiples of 3:

total = 0
skipped = 0

for number in range(1, 21):
    if number % 3 == 0:
        skipped = skipped + 1
        continue           # jump straight to the next number
    total = total + number

print(f"total {total}, skipped {skipped}")

Notice that continue did not save any work in the big-picture sense — the loop still visited all 20 numbers, so the step count is still n. It changed what happens on a pass, not how many passes there are. Keep that separation clear: skipping an item is not the same as never visiting it.

3.7Common mistakes with loops

Four loop bugs account for most of the confusion in these first weeks. Meet them here so you recognise them in your own cells tonight.

The second one is subtle enough to show. Both loops below look reasonable; only one gives the right total for 1 to 5, which is 15:

# WRONG: total is wiped clean on every pass
for number in range(1, 6):
    total = 0
    total = total + number
print("wrong version:", total)      # prints 5, not 15

# RIGHT: total starts at 0 once, then grows
total = 0
for number in range(1, 6):
    total = total + number
print("right version:", total)      # prints 15

In the wrong version, every pass throws the running total away and rebuilds it from zero, so at the end it only holds the last number. The lesson is the one-line habit: initialise accumulators above the loop. When a total or a counter comes out wrong, this is the first place to look.

3.10Optional Studio Extension

3.11Words from this week

3.12Chapter problem set — Skiena 2.10

These are exercises from Skiena's Algorithm Design Manual, Chapter 2, matched to this week and solved step by step. They are all about the same skill you practised above: counting how many times a loop runs, and turning that count into a tidy formula.

for i in range(1, n + 1):          # i = 1, 2, ..., n
    for j in range(i, 2 * i + 1):  # j = i, i+1, ..., 2i
        print("foobar")

for n in range(1, 6):
    steps = 0
    for i in range(1, n + 1):
        for j in range(i, 2 * i + 1):
            steps = steps + 1              # one "foobar"
    formula = (n * n + 3 * n) // 2
    print(f"n = {n}: counted {steps}, formula {formula}")

for k in range(1, 21):
    left = sum((-1) ** (i - 1) * i * i for i in range(1, k + 1))
    right = (-1) ** (k - 1) * k * (k + 1) // 2
    print(k, left, right, left == right)

for n in (1, 2, 3, 4, 12):
    total = 0
    for d in range(1, n + 1):
        total = total + d * (d + 1) // 2   # presents delivered on day d
    formula = n * (n + 1) * (n + 2) // 6
    print(f"n = {n}: total {total}, formula {formula}")