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
- linear search — Finding an item by checking each element in turn from the start until it matches or the list ends.
- growth rate — The rule that says how fast an algorithm's cost rises as the input size n rises, such as constant, linear or quadratic.
- quadratic time — Work that grows with the square of the input, written O(n^2): twice the items, four times the work.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers
- Choosing The Right Sequence — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers