9. Complexity

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil -- Donald Knuth


9.1. Rationale

  • Podstawy optymalizacji i wydajności systemów

  • Computational Complexity (pol. złożoność obliczeniowa)

  • Memory Complexity (pol. złożoność pamięciowa)

  • Cognitive Complexity (pol. złożoność kognitywna)

  • Cyclomatic Complexity (pol. złożoność cyklometryczna)

  • Big O notation 1

  • https://wiki.python.org/moin/TimeComplexity


9.2. Computational Complexity

9.3. Memory Complexity

9.4. Cognitive Complexity

9.5. Cyclomatic Complexity

  • Measures the minimum number of test cases required for full test coverage.

9.6. Big O notation

Most common:

  • O(sqrt_n)

  • O(log_n)

  • O(log2_n)

  • O(1)

  • O(n)

  • O(nlog2_n)

  • O(n^2)

  • O(2^n)

  • O(n!)

Table 9.2. Table of common time complexities 1

Running time (T(n))


Example algorithms


constant time

Finding the median value in a sorted array of numbersCalculating (−1)n


inverse Ackermann time

Amortized time per operation using a disjoint set

O(log* n)

iterated logarithmic time

Distributed coloring of cycles

O(log log n)


Amortized time per operation using a bounded priority queue

O(log n)

logarithmic time

Binary search

poly(log n)

polylogarithmic time

O(nc) where 0 < c < 1

fractional power

Searching in a kd-tree


linear time

Finding the smallest or largest item in an unsorted array, Kadane's algorithm, linear search

O(n log* n)

n log-star n time

Seidel's polygon triangulation algorithm

O(n log n)

linearithmic time

Fastest possible comparison sort; Fast Fourier transform

n poly(log n)

quasilinear time


quadratic time

Bubble sort; Insertion sort; Direct convolution


cubic time

Naive multiplication of two n×n matrices. Calculating partial correlation

2O(log n) = poly(n)

polynomial time

Karmarkar's algorithm for linear programming; AKS primality test

2poly(log n)

quasi-polynomial time

Best-known O(log2 n)-approximation algorithm for the directed Steiner tree problem

O(2nε) for all ε > 0

sub-exponential time

Best-known algorithm for integer factorization; formerly-best algorithm for graph isomorphism


sub-exponential time

Best-known algorithm for integer factorization; formerly-best algorithm for graph isomorphism


exponential time (with linear exponent)

Solving the traveling salesman problem using dynamic programming


exponential time

Solving matrix chain multiplication via brute-force search


factorial time

Solving the traveling salesman problem via brute-force search


double exponential time

Deciding the truth of a given statement in Presburger arithmetic

9.7. References



9.8. Further Reading