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 n_{0} such that
f (n) Cg(n)
nn_{0}

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(n^{k}) (k fixed) refers to polynomial time;
O(log n) is called logarithmic time; O(2^{n})
refers to exponential time, etc.
eEL,CSA_Dept,IISc,Bangalore