Best, Worst and Average Case Analysis

Best, Worst and Average Case Analysis

• Best case time complexity :

If an algorithm takes minimum amount of time to run to completion for a specific set of input then it is called best case time complexity. For example ‒ While searching a particular element by using sequential search we get the desired element at first place itself then it is called best case time complexity.

• Worst case time complexity :

If an algorithm takes maximum amount of time to run to completion for a specific set of input then it is called worst case time complexity. For example ‒ While searching an element by using linear searching method if desired element is placed at the end of the list then we get worst time complexity.

• Average case time complexity :

The time complexity that we get for certain set of inputs is as a average same. Then for corresponding input such a time complexity is called average case time complexity.

• Algorithmic example :

Consider following algorithm. This algorithm is for sequential search.

Algorithm Seq_search(A[0... n‒1 ],key)

// Problem Description: This algorithm is for searching the

//key element from an array A[0...n‒1] sequentially.

for i= 0 to n‒1 do

if(A[i]=key)then

return i

Analysis

1. Best case analysis :

In above searching algorithm the element key is searched from the list of n elements. If the key element is present at first location in the list(A[0...n‒1]) then algorithm run for a very short time and thereby we will get the best case time complexity. Hence in terms of big‒oh notation the time complexity can be denoted as

T(n) = O(1)

2. Worst case analysis :

Worst case time complexity is a time complexity when algorithm runs for a longest time. In above searching algorithm the element key is searched from the list of n elements. If the key element is present at nth location then clearly the algorithm will run for longest time and thereby we will get the worst case time complexity. We can denote the worst case time complexity as

T(n) = n

Hence in terms of big‒oh notation the time complexity can be denoted as

T(n) = O(n)

3. Average case analysis :

This type of complexity gives information about the behaviour of an algorithm on specific or random input. We can compute the average case time complexity as follows ‒

Let,

P be a probability of getting successful search.

n is the total number of elements in the list.

• The first match of the element will occur at ith location. Hence probability of occurring first match is P/n for every i^th element.

• The probability of getting unsuccessful search is (1 ‒ p).

• Now, we can find average case time complexity T(n) as ‒

T(n) = Probability of successful search + Probability of unsuccessful search

T(n) = (1 p/n + 2 p/n + ....+ i p/n) + n.(1‒P)

= p/n (1+2+...+i) + n.(1‒P)

= p/n  n(n+1)/ 2 + n.(1‒P)

T(n) = P (n+1)/2 + n.(1‒P)

This is general formula for computing average case time complexity.

In equation (3.4.1) we will put different values of P

If     P = 0, we get

T(n) = 0 (n+1)/2 + n (1‒0)

T(n) = n

If P =1, we get

T(n) =1(n+1)/2 + n.(1‒1)

T(n) = (n+1) / 2

That means the algorithm scans about the half of the elements from the list.

Hence time complexity can be denoted in terms of big oh notation as

T(n) = O(n)

Hence we can summarize the time complexity of sequential search in best case, worst case and average case in the form of Big‒oh notation as

Best Case ‒ O(1)

Worst Case ‒ O(n)

Average Case ‒ O(n)