Arrays and Iteration

Array Sum (Linear Scan)

Walk an array once, accumulating each element into a running total. This is the canonical single-pass linear scan and the simplest possible loop invariant: after step i, total equals the sum of arr[0..i].

Algorithm

The canonical input from the lesson spec is arr = [3, 1, 4, 1, 5, 9, 2, 6]. After eight passes the running total is 31.

linear scan Visit each element exactly once in index order.
running total `total` accumulates the sum as the loop advances.

Basic Implementation

basic.py
Replay: real traced execution (multi-file project)
arr = [3, 1, 4, 1, 5, 9, 2, 6]
total = 0
for i in range(len(arr)):
    total = total + arr[i]
print(total)

  1. arr ← [3, 1, 4, 1, 5, 9, 2, 6]

    1arr = [3, 1, 4, 1, 5, 9, 2, 6]2total = 0
    values this step[3, 1, 4, 1, 5, 9, 2, 6]arr

  2. total ← 0

    1arr = [3, 1, 4, 1, 5, 9, 2, 6]2total = 03for i in range(len(arr)):
    values this step0total[3, 1, 4, 1, 5, 9, 2, 6]arr

  3. total ← 3

    3for i in range(len(arr)):4    total = total + arr[i]5print(total)
    values this step0 → 3total0i3arr[i]

  4. total ← 4

    3for i in range(len(arr)):4    total = total + arr[i]5print(total)
    values this step3 → 4total1i1arr[i]

  5. total ← 8

    3for i in range(len(arr)):4    total = total + arr[i]5print(total)
    values this step4 → 8total2i4arr[i]

  6. total ← 9

    3for i in range(len(arr)):4    total = total + arr[i]5print(total)
    values this step8 → 9total3i1arr[i]

  7. total ← 14

    3for i in range(len(arr)):4    total = total + arr[i]5print(total)
    values this step9 → 14total4i5arr[i]

  8. total ← 23

    3for i in range(len(arr)):4    total = total + arr[i]5print(total)
    values this step14 → 23total5i9arr[i]

  9. total ← 25

    3for i in range(len(arr)):4    total = total + arr[i]5print(total)
    values this step23 → 25total6i2arr[i]

  10. total ← 31

    3for i in range(len(arr)):4    total = total + arr[i]5print(total)
    values this step25 → 31total7i6arr[i]

Trace Output

trace.py 
arr = [3, 1, 4, 1, 5, 9, 2, 6]
total = 0
for i in range(len(arr)):
    before = total
    total = total + arr[i]
    print(f"step {i}: arr[{i}]={arr[i]} total {before} -> {total}")
print(f"final total = {total}")

Complexity

  • Time: O(n)
  • Space: O(1)

Implementation notes

  • Python: use the explicit for loop. Calling sum() would hide the iteration the lesson is teaching.
  • The replay shows i, arr[i], and total before and after each addition, matching the lesson spec's state-transition table.