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

Taught in

References