Arrays and Iteration

Array Sum (Linear Scan)

Walk a vector 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[1..i].

Algorithm

The canonical input from the lesson spec is arr <- c(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.R
Replay: real traced execution (multi-file project)
arr <- c(3, 1, 4, 1, 5, 9, 2, 6)
total <- 0
i <- 1
while (i <= length(arr)) {
	total <- total + arr[i]
	i <- i + 1
}
cat(total, "\n", sep = "")

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

    1arr <- c(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 <- c(3, 1, 4, 1, 5, 9, 2, 6)2total <- 03i <- 1
    values this step0total[3, 1, 4, 1, 5, 9, 2, 6]arr

  3. total ← 3

    4while (i <= length(arr)) {5	total <- total + arr[i]6	i <- i + 1
    values this step0 → 3total1i3arr[i]

  4. total ← 4

    4while (i <= length(arr)) {5	total <- total + arr[i]6	i <- i + 1
    values this step3 → 4total2i1arr[i]

  5. total ← 8

    4while (i <= length(arr)) {5	total <- total + arr[i]6	i <- i + 1
    values this step4 → 8total3i4arr[i]

  6. total ← 9

    4while (i <= length(arr)) {5	total <- total + arr[i]6	i <- i + 1
    values this step8 → 9total4i1arr[i]

  7. total ← 14

    4while (i <= length(arr)) {5	total <- total + arr[i]6	i <- i + 1
    values this step9 → 14total5i5arr[i]

  8. total ← 23

    4while (i <= length(arr)) {5	total <- total + arr[i]6	i <- i + 1
    values this step14 → 23total6i9arr[i]

  9. total ← 25

    4while (i <= length(arr)) {5	total <- total + arr[i]6	i <- i + 1
    values this step23 → 25total7i2arr[i]

  10. total ← 31

    4while (i <= length(arr)) {5	total <- total + arr[i]6	i <- i + 1
    values this step25 → 31total8i6arr[i]

Trace Output

trace.R
Replay: real traced execution (multi-file project)
arr <- c(3, 1, 4, 1, 5, 9, 2, 6)
total <- 0
i <- 1
while (i <= length(arr)) {
	before <- total
	total <- total + arr[i]
	cat(sprintf("step %d: arr(%d)=%d total %d -> %d\n", i, i, arr[i], before, total))
	i <- i + 1
}
cat(sprintf("final total = %d\n", total))

  1. total ← 3, stdout ← step 1: arr(1)=3 total 0 -> 3

    5before <- total6total <- total + arr[i]7cat(sprintf("step %d: arr(%d)=%d total %d -> %d\n", i, i, arr[i], before, total))
    values this step3totalstep 1: arr(1)=3 total 0 -> 3stdout0before3arr[i]

  2. total ← 4, stdout ← step 2: arr(2)=1 total 3 -> 4

    5before <- total6total <- total + arr[i]7cat(sprintf("step %d: arr(%d)=%d total %d -> %d\n", i, i, arr[i], before, total))
    values this step4totalstep 2: arr(2)=1 total 3 -> 4stdout3before1arr[i]

  3. total ← 8, stdout ← step 3: arr(3)=4 total 4 -> 8

    5before <- total6total <- total + arr[i]7cat(sprintf("step %d: arr(%d)=%d total %d -> %d\n", i, i, arr[i], before, total))
    values this step8totalstep 3: arr(3)=4 total 4 -> 8stdout4before4arr[i]

  4. total ← 9, stdout ← step 4: arr(4)=1 total 8 -> 9

    5before <- total6total <- total + arr[i]7cat(sprintf("step %d: arr(%d)=%d total %d -> %d\n", i, i, arr[i], before, total))
    values this step9totalstep 4: arr(4)=1 total 8 -> 9stdout8before1arr[i]

  5. total ← 14, stdout ← step 5: arr(5)=5 total 9 -> 14

    5before <- total6total <- total + arr[i]7cat(sprintf("step %d: arr(%d)=%d total %d -> %d\n", i, i, arr[i], before, total))
    values this step14totalstep 5: arr(5)=5 total 9 -> 14stdout9before5arr[i]

  6. total ← 23, stdout ← step 6: arr(6)=9 total 14 -> 23

    5before <- total6total <- total + arr[i]7cat(sprintf("step %d: arr(%d)=%d total %d -> %d\n", i, i, arr[i], before, total))
    values this step23totalstep 6: arr(6)=9 total 14 -> 23stdout14before9arr[i]

  7. total ← 25, stdout ← step 7: arr(7)=2 total 23 -> 25

    5before <- total6total <- total + arr[i]7cat(sprintf("step %d: arr(%d)=%d total %d -> %d\n", i, i, arr[i], before, total))
    values this step25totalstep 7: arr(7)=2 total 23 -> 25stdout23before2arr[i]

  8. total ← 31, stdout ← step 8: arr(8)=6 total 25 -> 31

    5before <- total6total <- total + arr[i]7cat(sprintf("step %d: arr(%d)=%d total %d -> %d\n", i, i, arr[i], before, total))
    values this step31totalstep 8: arr(8)=6 total 25 -> 31stdout25before6arr[i]

  9. stdout ← final total = 31

    9}10cat(sprintf("final total = %d\n", total))
    values this stepfinal total = 31stdout31total

Complexity

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

Implementation notes

  • R: use the explicit while (i <= length(arr)) loop with total <- 0 and a manual 1-based index. The stdlib sum(arr) is vectorised in C and would hide the loop the lesson is teaching, and Reduce("+", arr, 0) would compress the running update into a single frame.
  • arr <- c(3, 1, 4, 1, 5, 9, 2, 6) documents the fixed-content vector; the manual i <- i + 1 step keeps the iteration without leaning on for (x in arr) that hides the running index.
  • R vectors are 1-indexed; the replay shows i, arr[i], and total before and after each addition, with i ranging 1..8 to match the actual loop counter.
  • cat(total, "\n", sep = "") prints the final scalar without the default index marker that print() would emit.