Complexity classes

Each class describes a growth bound under a stated cost model. Pick a class and inspect a representative runtime and memory example. Remember that one algorithm can have different time and space bounds.

Lessons and practical examples

• Constant (O(1)): A fixed amount of work or memory is required regardless of how large the input becomes.

• Cubic (O(n³)): The amount of work or memory cells grows with the cube of input size.

• Exponential (O(2ⁿ)): The number of possibilities doubles when one new independent yes/no choice is added.

• Factorial (O(n!)): The number of possible arrangements grows as the product 1 × 2 × … × n.

• Linear (O(n)): The amount of work or auxiliary storage grows in direct proportion to the number of elements.

• Linearithmic (O(n log n)): Roughly logarithmically many levels each process a total of n elements.

• Logarithmic (O(log n)): Each step removes a fixed fraction of the remaining possibilities, so the number of steps grows logarithmically.

• Quadratic (O(n²)): The work or stored cell count grows proportionally to the square of input size.

• Square root (O(√n)): The operation or memory count grows with the square root of a numeric magnitude n.

How to study this section

Start with one concept, work through a small example, and verify your prediction. Follow linked topics when a prerequisite or related idea needs more explanation.