Algorithm Analysis
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 (BigOh) notation.
BigOh 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 BigOh Notation?
1. It does not consider the programming effort.
2. It hides the important constants.
Name the different categories of algorithms based on BigOh Notation
According to BigOh 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.
http://
http://
Contributed by:
Rohit kakria
I am software developer
Resourse address on xpode.com
http://www.xpode.com/Print.aspx?Articleid=131
Click here to go on website
