[prev] 9 [next]

Algorithmic Complexity

Cost is primarily interesting for large data
  • consider growth rate rather than absolute cost
Leads to complexity classes and big-O notation

Definition:   g(n) ∈ O(f(n))   if g(n) ≤ c.f(n)   ∀ n > N0

Complexity classes

  • O(1) ... constant functions  (e.g. g(n) = 1, 2, 3, ...)
  • O(logn) ... log functions  (e.g. log(n), log2(n), ...)
  • O(n) ... linear functions  (e.g. n/2, n, 5n+100, ...)
  • O(nlogn),   O(n2),   O(n3),   O(kn),   O(n!),   ...