linear time

Work that grows in direct proportion to the input, written O(n): twice the items, twice the work.

In more detail

Scanning a list, summing its values or copying it are linear because each item is touched a fixed number of times. Many problems cannot be solved faster than linear time, since every item must at least be read once. Linear is usually acceptable; the trouble starts when a linear step sits inside another loop.

Related terms

Taught in

References