Worst, Average and Best Case Analysis of Algorithms

Introduction: 

We all understand that as the input size (n) grows, an algorithm's running time grows. Even though the input is the same size, running times can change between distinct input instances. We then conduct best, average, and worst-case analyses in that situation. In this post, we will take an example of Linear Search and will analyze its best, average, and worst-case time complexity.

Consider the linear search example where we look for an item in an array. In Linear search, we simply traverse the list completely and match each element of the list with the item whose location is to be found. If the match is found, then the location of the item is returned; otherwise, the algorithm returns -1. The steps used in the implementation of Linear Search are listed as follows -

  • First, we have to traverse the array of elements using a for a loop.
  • In each iteration of for loop, compare the search element with the current array element, and -
    • If the element matches, then return the index of the corresponding array element.
    • If the element does not match, then move to the next element.
  • If there is no match or the search element is not present in the given array, return -1.

.

Worst Case Analysis: 

It put the upper bound on the running time of an algorithm. In order to find the worst-case complexity for an algorithm, we must know the case which causes the maximum number of operations to be performed. For example, for linear search, the worst case is when the item to be searched is not present in the array. For example, for linear search, the worst case is when the item to be searched is not present in the array. The for loop will run n times as we will compare item to be searched with all the elements one by one. So the complexity, in this case, O(n).

 

 

Best Case Analysis: 

It put the lower bound on the running time of an algorithm. We must know the case that causes the minimum number of operations to be performed. For example, for linear search, the best case is when the item we are looking for is in the very first position of the array, it will return the index immediately. The for loop runs only once. So the complexity, in this case, will be 


Average Case Analysis:

In average case analysis, we take all possible inputs and calculate the computing time for all of the inputs. Sum all the calculated values and divide the sum by the total number of inputs. We must know (or predict) the 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 the array). So, we sum all the cases and divide the sum by (n+1). Following is the value of average-case time complexity:

 



                                                           

Comments

Post a Comment

Popular posts from this blog

Asymptotic Analysis

Introduction: If you want to analyze two algorithms how you will measure them- The simplest way to do it is to implement both the algorithms run them on some machine and check which one is faster. But there are so some problems associated with this approach:        For some input algorithm A may perform well and for some input algorithm B may perform well.     For some input algorithm  A,  is performing good on machine X but for the same input on machine Y algorithm B is doing good All such problems can be handled using the asymptotic notation as in asymptotic notation the performance of the algorithm is measured in terms of input size. How the performance of algorithms grows as the input size grows. The machine-dependent constants can always be ignored after a certain value of input size.   Does it always work? Asymptotic notation does not do good always for example .      Two algorithms with the sa...
Read more

Complexity of Loops

The time complexity of a function is O(1) if does not contain a loop, recursive function, or any other non-constant time function.  The time complexity of a loop is also O(1) if it has a constant no of iterations Recursive function time complexity is also O(1) if it runs a constant no of times. Linear Loops: The time complexity of a loop is O(n) which is linear. If the loop variable is incremented or decremented by constant Nested Loops:  1. The time complexity of nested loops is equal to the number of times the innermost statement is executed. For example, the following sample loop has  O(n 2 )  time complexity:    for (int i = 1; i <=n; i += c) {        for (int j = 1; j <=n; j += c) {           // some O(1) expressions        }    }   2. When one of the loops is divided and multiplied by constant and other loop is increm...
Read more