Asymptotic Analysis [Worst , Average & Best cases]

                                                        Algorithm 
      Page:1    

                             
An Algorithm is a step by step procedure, which defines the set of instructions to be performed in a certain order to get the desired output from those in algorithms.
An algorithm are generally analyzed on two factors − time and space. It means, how much execution time and how much extra space taken by the algorithm to execute.

                Asymptotic Analysis

ASYMPTOTIC ANALYSIS is the big idea that handles the above issues in analyzing algorithms. In Asymptotic Analysis we calculate the performance of an algorithm in terms of input size (we don't measure the actual running time). We calculate, how does the time (or space) taken by an algorithm increases with the input size.

 There are three cases to analyze an algorithm:

1. Worst Case
2. Average Case
3. Best Case

Let us consider the following implementation of Linear Search.

#include <stdio.h>

// Linearly search x in arr [l. If x is present then return the index,

// otherwise return -1

int search (int arr [], int n, int x)

int i;

for (i=0; i<n; i++)

{

if (arr [il == x)

return i;

return -1;

/* Driver program to test above functions*/

int main ()

int arr [i = {1, 10, 30, 15}

int x = 30;

int n = sizeof (arr) /sizeof (arr [o]);

printf ("*d is present at index &d", x, search (arr, n, x))

get char ()

return 0;

Worst Case Analysis 

In the worst case analysis,we get the following informations:-

1.we calculate  upper bound on running time of an algorithm. 

2.We must know the case that causes maximum number of operations to be executed. 

3. For Linear Search, the worst case happens when the element to be searched (x in the above code) is not present in the array (or) last element, the search functions compares it with all the elements of arr[ ] one by one. Therefore, the worst case time complexity of linear Sarch would be Θ(n). 

 Average case analysis 

In average case analysis:
1.we take all possible inputs and calculate computing time for all of the inputs.

2. Sum all the calculated values divide the sum by total number of inputs. 

3.We must know (or predict) distribution of cases.
↪ For the linear search problem, let us assume that all cases are uniformly distributed (including the case of x not being present in array). So we sum all the cases and divide the sum by (n + 1). Given below is the value of average case time complexity.
             

Best Case Analysis 

 In the best case analysis:
 1. We calculate lower bound on running time of an algorithm.
2. We must know the case that causes minimum number of operations to be executed.
3. In the linear search problem, the best case occurs when x is present at the first               location. 
4. The number of operations in the best case is constant (not dependent on n). So time complexity in the best case would be Θ(1).
5. Most of the times, we do worst case analysis to analyze algorithms. In the worst analysis, we guarantee an upper bound on the running time of fan algorithm which is good information. 
6.The average case analysis is not easy to do in most of the practical cases and it is rarely done. 
7.In the average case analysis, we must know (or predict) the mathematical distribution of all possible inputs. The Best Case analysis is bogus. Guaranteeing a lower bound on an algorithm doesn't provide any information as in the worst case, an algorithm may take years to execute.

Simply click on read more option to get notes on Asymptotic Notations.

Continue....

Asymptotic Notations