Suppose M is an algorithm and suppose n is the size of input data. The complexity function f (n) of M increases as n increases. The rate of increase of f (n) is found by comparing f (n) with some standard functions, such as:
log2 n, n, n log2 n, n2, n3, 2n
One way to compare the function f (n) with these functions is to use the functional O notation i.e. Big O (Big-Oh) notation.
Big-Oh notation is used to measure the properties of the algorithms such as performance and / or memory requirements in general fashion. To measure the algorithmic complexity the constant factors are not considered during the analysis.
Suppose f (n) and g (n) are functions which are defined on the +ive integers with the property that f (n) is bounded by some multiple of g (n) for almost all n i.e. suppose there exists a +ive integer k and a +ive number M such that for all n > k, we have:
¦f (n)¦ = M ¦g(n)¦
Then we can write:
f (n) = O (g (n) )
For example, we have following two functions:
f (n): 100n2
g (n): 5n3
These functions will take following amount of time for different values of n:
n f (n) g(n)
1 100 5
5 2500 625
10 10000 5000
20 40000 40000
30 90000 135000
In this case, f (n) = g (n) for all n = 20, but f (n) = g (n) for all n > 20. So g (n) provides upper bound on f (n) because f (n) cannot have more value than g (n) when n > 20.
What are the limitations of Big-Oh Notation?
1. It does not consider the programming effort.
2. It hides the important constants.
Name the different categories of algorithms based on Big-Oh Notation
According to Big-Oh notation the algorithms can be divided into following categories:
1. Constant Time (O (1)) Algorithms.
2. Logarithmic Time (O (log n)) Algorithms.
3. Linear Time (O (n)) Algorithms.
4. Polynomial Time (O (nk), for k>1) Algorithms.
5. Exponential Time (O (kn), for k>1) Algorithms
Terms Worst Case, Average Case and Best Case Analysis:
Worst Case:
It gives the maximum value of complexity function f (n) for any possible input.
Average Case:
It gives the expected value of complexity function f (n) for any possible input.
Best Case:
It gives the minimum value of complexity function f (n) for any possible input.