Repeating Work: Loops and a Step Counter

for i in range(10, 0, -1):
    print(i)
print("Lift off")

Ten steps for a countdown from 10, a hundred from 100: the work is proportional to where you start.

n = 100
evens = 0
steps = 0

for number in range(1, n + 1):
    steps = steps + 1
    if number % 2 == 0:
        evens = evens + 1

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

Steps: 100, 200, 400 — exactly n. Answer: 50, 100, 200. Both grow in a straight line, and doubling n doubles both.

90 000. If you guessed 600 you added when you should have multiplied — a nested loop multiplies, and that single mistake is behind most "why is my program frozen?" questions.

10, 14, 17, 20. Multiplying the input by ten adds only three or four steps. Compare that with the nested-loop table above — these two behaviours are as different as walking and teleporting.

steps = 0
answer = None

for k in range(1, 1000):
    steps = steps + 1
    if k % 7 == 0 and k % 9 == 0:
        answer = k
        break

print(f"answer {answer}, checked {steps}")

63 is 7 × 9, the first number both divide, so the loop stops after checking 63. Without break it would have run all the way to 999.

for n in range(1, 21):
    if n % 3 == 0 and n % 5 == 0:
        print("FizzBuzz")
    elif n % 3 == 0:
        print("Fizz")
    elif n % 5 == 0:
        print("Buzz")
    else:
        print(n)

The order of the branches is the whole trick: test "both" first, because a multiple of 15 is also a multiple of 3, and Python takes the first true branch. Put the "Fizz" test first and 15 would wrongly print "Fizz".

Start with one pass of the outer loop. Fix a value of i. The inner loop runs j from i up to and including 2*i. How many whole numbers are there from i to 2*i? Count them: it is (2i − i) + 1 = i + 1. The "+1" is the same off-by-one care from §3.2 — both ends are included, so you add one. Quick check with i = 3: j takes 3, 4, 5, 6 — that is four values, and i + 1 = 4. Good.

(a) Add up every pass of the outer loop. The outer loop does this for i = 1, 2, …, n, so we add i + 1 for each of those:

T(n) = ∑_i=1ⁿ (i + 1)

(b) Simplify. Split the sum into two easier sums:

T(n) = (1 + 2 + … + n) + (1 + 1 + … + 1)

The first bracket is the famous "add 1 up to n" from §3.2, which equals n(n+1)/2. The second bracket is just the number 1 added n times, which is n. So:

T(n) = n(n+1)/2 + n = (n² + n + 2n)/2 = (n² + 3n)/2

The biggest piece is the n², so for large n this grows like a nested loop should — it is Θ(n²), the two-loops-multiply behaviour from §3.5.

A step counter confirms the formula for small n:

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}")

Answer: (a) T(n) = ∑i=1n (i + 1); (b) T(n) = n(n+1)/2 + n = (n² + 3n)/2, which is Θ(n²).

What the statement says. On the left we add the squares 1, 4, 9, 16, … but flip the sign on every second one: plus, minus, plus, minus. The claim is that this messy-looking total is always just k(k+1)/2 — the plain "add 1 up to k" number — carrying a plus sign when k is odd and a minus sign when k is even (that is all (−1)k−1 does: it is +1 for odd k, −1 for even k).

Check the pattern for the first few k. The quickest way to trust an identity is to compute both sides on small cases and watch them line up:

Why it works — pair the terms. Group each minus with the plus just before it: (1² − 2²), then (3² − 4²), and so on. Each pair is a difference of squares, and there is a neat fact hiding in it:

(2m−1)² − (2m)² = −(4m − 1) = −(2m−1) − (2m)

In plain words, each plus-minus pair collapses to just the negative sum of the two numbers involved. So after pairing, the whole alternating sum of squares turns into a plain running total of 1, 2, 3, … (with a sign) — and a plain running total of 1 up to k is exactly k(k+1)/2. The sign at the end is whatever the last term carried: plus for odd k, minus for even k. That is the right-hand side. (If k is odd there is one unpaired plus term left over at the end, and the arithmetic still lands on the same formula — worth checking yourself as an optional challenge.)

A four-line check confirms both sides agree all the way to k = 20:

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)

Answer: the identity holds: 1² − 2² + … + (−1)k−1 k² = (−1)k−1 · k(k+1)/2, verified for k = 1…20 and explained by pairing consecutive terms.

How many arrive on a single day. On day d the true love delivers 1 + 2 + … + d presents (the first gift, plus the second, …, up to the d-th). That is the "add 1 up to d" number again, so a single day d brings d(d+1)/2 presents.

Add up all the days. The grand total over n days is the sum of each day's haul:

Total(n) = ∑_d=1ⁿ d(d+1)/2

A small table makes the running total concrete:

The closed form. Those running totals 1, 4, 10, 20, … are the tetrahedral numbers (imagine stacking triangular layers of cannonballs into a pyramid). The tidy formula for the sum above is:

Total(n) = n(n+1)(n+2)/6

Check it against the table: n = 4 gives 4·5·6/6 = 20. For the real song, n = 12: 12·13·14/6 = 2184/6 = 364 — one present for (almost) every day of the year. A tiny program agrees:

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}")

Notice the highest power is n³, so the present count grows like Θ(n³) — even faster than the nested-loop Θ(n²) tables of §3.5.

Answer: Total(n) = ∑d=1n d(d+1)/2 = n(n+1)(n+2)/6, which for n = 12 is 364 presents. The growth is Θ(n³).