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

Algorithm

Trace Output

basic.lua 
local arr = {3, 1, 4, 1, 5, 9, 2, 6}
local total = 0
local i = 1
while i <= #arr do
	total = total + arr[i]
	i = i + 1
end
print(total)
trace.lua 
local arr = {3, 1, 4, 1, 5, 9, 2, 6}
local total = 0
local i = 1
while i <= #arr do
	local before = total
	total = total + arr[i]
	print(string.format("step %d: arr(%d)=%d total %d -> %d", i, i, arr[i], before, total))
	i = i + 1
end
print(string.format("final total = %d", total))

Complexity

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

Implementation notes

  • Lua: use the explicit while i <= #arr do loop with total = 0 and a manual 1-based index. The stdlib does not ship a one-call sum for sequences — even table.unpack(arr) would just spread the data; we keep the loop visible.
  • local 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 ipairs or for k, v in ipairs(arr) do that hide the running update.
  • Lua tables 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.
linear scan Visit each element exactly once in index order.
running total `total` accumulates the sum as the loop advances.