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.sh

#!/usr/bin/env bash
set -euo pipefail
arr=(3 1 4 1 5 9 2 6)
total=0
i=0
while [ "$i" -lt "${#arr[@]}" ]; do
	total=$((total + arr[i]))
	i=$((i + 1))
done
echo "$total"

trace.sh

#!/usr/bin/env bash
set -euo pipefail
arr=(3 1 4 1 5 9 2 6)
total=0
i=0
while [ "$i" -lt "${#arr[@]}" ]; do
	before=$total
	total=$((total + arr[i]))
	printf 'step %d: arr(%d)=%d total %d -> %d\n' "$i" "$i" "${arr[i]}" "$before" "$total"
	i=$((i + 1))
done
printf 'final total = %d\n' "$total"

Complexity

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

Implementation notes

Bash: use the explicit while [ "$i" -lt "${#arr[@]}" ] loop with total=0 and a manual 0-based index. Bash has no built-in sum primitive; piping to awk '{ s += $1 } END { print s }' would push the loop into another process the lesson is not teaching, and printf '%s+' "${arr[@]}" 0 | bc would defer the running update to bc and hide it.
arr=(3 1 4 1 5 9 2 6) documents the fixed-content array; the manual i=$((i + 1)) step keeps the iteration without leaning on for v in "${arr[@]}" that hides the running index.
set -euo pipefail at the top keeps every typo and unset variable loud, and arithmetic uses $((...)) expansion so the assignments never trip set -e.
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.