Complexity of AlgorithmsPrevious:1.2
Complexity of Algorithms
1.2.1 Big Oh Notation
Let n be the size of the input and f (n), g(n)
be positive functions of n.
A convenient way of describing the growth rate of a function and hence
the time complexity of an algorithm.
DEF.Big Oh. f
(n) is O(g(n))
if and only if there exists a real, positive constant Cand
a positive integer n0 such that
f (n) Cg(n)
Note that O(g(n)) is a class of functions.
The "Oh" notation specifies asymptotic upper bounds
O(1) refers to constant time. O(n) indicates linear
time; O(nk) (k fixed) refers to polynomial time;
O(log n) is called logarithmic time; O(2n)
refers to exponential time, etc.