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 (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.

Click here to go on website