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

Trace Output

basic.py

arr = [3, 1, 4, 1, 5, 9, 2, 6]
total = 0
for i in range(len(arr)):
    total = total + arr[i]
print(total)

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.

linear scan Visit each element exactly once in index order.

running total `total` accumulates the sum as the loop advances.