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.
In more detail
The five rates met most often are constant O(1), logarithmic O(log n), linear O(n), log-linear O(n log n) and quadratic O(n^2). You can usually read the rate from the shape of the code: one loop is linear, a loop inside a loop over the same data is quadratic, and halving the problem each step is logarithmic. Growth rate matters more than raw speed once n is large.
Related terms
- constant time — Work that stays the same no matter how large the input is, written O(1).
- logarithmic time — Work that grows by only one step each time the input doubles, written O(log n), typical of algorithms that halve the problem each step.
- linear time — Work that grows in direct proportion to the input, written O(n): twice the items, twice the work.
- log-linear time — Work that grows as n times log n, written O(n log n), the typical cost of efficient comparison sorting.
- quadratic time — Work that grows with the square of the input, written O(n^2): twice the items, four times the work.
- exponential time — Work that roughly doubles each time the input grows by one, written O(2^n), which becomes impossible to finish for even modest inputs.
Taught in
- Why Complexity Matters In Production — Algorithms & Data Structures for Working Engineers
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers
- Arrays: Contiguous Memory And Constant-Time Access — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers