Linear
Linear time means the work grows in direct proportion to the input. One loop over an array of length n usually means n steps, so we write O(n).
function total(values) {
let sum = 0;
for (const value of values) {
sum += value;
}
return sum;
}
Array methods such as map, filter, and reduce also walk the array once, so they are linear as well. Two separate loops are still linear, because constants are dropped: O(2n) becomes O(n).
The trouble starts when a loop contains another loop over the same input. That is where the next runtime comes from.
References and further reading
- MDN: for ofThe loop used in the example.
- MDN: Array mapA linear array method.