# 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.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))

Name

Example algorithms

O(1)

constant time

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

O(α(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)

log-logarithmic

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

O(n)

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

O(n2)

Bubble sort; Insertion sort; Direct convolution

O(n3)

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

2o(n)

sub-exponential time

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

2O(n)

exponential time (with linear exponent)

Solving the traveling salesman problem using dynamic programming

2poly(n)

exponential time

Solving matrix chain multiplication via brute-force search

O(n!)

factorial time

Solving the traveling salesman problem via brute-force search

22poly(n)

double exponential time

Deciding the truth of a given statement in Presburger arithmetic