Skip to content
Lydia Hallie theavocoder
Big O contents
Big O Notation / O(n)

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