HTML Asp.Net 2.0 C++ Programs/Algorithms ASP.NET 2.0 & 3.5 / Ajax Design Patterns Sql Server Website Hosting .Net Video Tutorials Javascript jQuery & ASP.NET General Concepts C++ Concepts Usable Codes Google Stuff Tips & Tricks (Fun Stuff) Errors : Asp.Net Errors : Sql Server HTML Software Testing J2EE Struts Data Structures Data Structures Programs/Algorithms C# Concept Quick Test Professional (QTP) WCF .net asp.net Java/J2EE Oops SQL C# Interview questions ADO.NET C# Interview Technical Analysis ,net

## 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): 100n2g (n): 5n3`

These functions will take following amount of time for different values of n:

`				n		f (n)		g(n)1		100		55		2500		62510		10000		500020		40000		4000030		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. 