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!), ...
|