Time complexity

  • Constant
  • Logarithmic
  • Linear
    • Sub- and super-linear
  • Polynomial
    • Example: nub
  • Improvement
  • Exponential

The only way to really know how fast code runs is to run it. But we can also achieve a great deal through reasoning. Especially for “collections” libraries,A few examples of collections libraries: containers, unordered-containers, vector it is common to describe the efficiency of an operation by giving a rough idea of the relationship between the number of elements in a collection and the time required to compute the operation.

The terminology for this comes from the field of asymptotic analysis, which contains a lot to learn. But for everyday programming, these are the top five words you should be familiar with:

Mathematically Informally
Constant 1 Fast
Logarithmic log n Pretty fast
Linear n Noticeable
Polynomial n2 Unpleasant
Exponential 2n Unusable

Sign up for access to the full page, plus the complete archive and all the latest content.