Click here to hide categories Click here to show left categories

User: Home          welcome : Guest          Log In / Register here     




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.

Share this article   |    Print    |    Article read by 1857 times
Author:
Rohit kakria
I am software developer
Related Articles: No related article
Related Interview Questions: No related interview question