It is very convenient to classify algorithms based on the relative amount of time or relative amount of space they require and specify the growth of time / space requirements as a function of the input size. Thus we have the notions of
– Time Complexity : Running time of the program as a function of size of the input.
–Space Complexity : Amount of computer memory required during the program exicution.
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 : f(n) is O(g(n)) if and only if there exits a real , positive constant C and a positive integer m such that
f(n) ≤ C × g(n) for all n>m
1)note that O(g(n)) is a class of functions.
2)the big Oh notation specifies asymptotic upper bounds.
3)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.
Let f(n) = n² + n +5
then f(n) is O(n²)
f(n) is O(n³)
f(n) is not O(n)