Next:1.2.2 ExamplesUp:1.2 Complexity of AlgorithmsPrevious:1.2 Complexity of Algorithms

1.2.1 Big Oh Notation

A convenient way of describing the growth rate of a function and hence the time complexity of an algorithm.
Let n be the size of the input and f (n), g(n) be positive functions of n.

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$\displaystyle \leq$Cg(n$\displaystyle \forall$   n$\displaystyle \geq$n0