Page 40 - DCAP407_DATA_STRUCTURE

Unit 2: Complexity Analysis

2.3.1 Types of Analysis

The efficiency of some algorithms may vary for inputs of the same size. For such algorithms, we need to
differentiate between the worst case, average case and best case efficiencies.
Best Case Analysis

If an algorithm takes the least amount of time to execute a specific set of input, then it is called the best
case time complexity. The best case efficiency of an algorithm is the efficiency for the best case input of
size n. Because of this input, the algorithm runs the fastest among all the possible inputs of the same
size.
To analyze the best case efficiency, we have to first determine the kind of inputs for which the count
C(n) will be the smallest among all possible inputs of size n. Then, we ascertain the value of C(n) on the
most convenient inputs.

In case of sequential search, the best case for lists of size n is when their first
elements are equal to the search key. Then,
C best (n) = 1

Best case does not mean the smallest input. It means the input of size n for which the
algorithm runs the fastest.

Average Case Analysis
If the time complexity of an algorithm for certain sets of inputs are on an average, then such a time
complexity is called average case time complexity.
Average case analysis provides necessary information about an algorithm’s behavior on a typical or
random input. You must make some assumption about the possible inputs of size n to analyze the
average case efficiency of algorithm.

Assume that in case of sequential search, the probability of successful search is
equal to t i.e. 0 ≤ t ≤ 1, and the probability of the first match occurring in the i th
position of the list is the same for all values of i. From these assumptions we
can easily find out the average number of key comparisons C avg (n).
In case of successful search, the probability of the first match occurring in the
t
i th position of the list is for all values of i and the comparison made by the
n
algorithm is also i.
In case of unsuccessful search, the number of comparison is n with the
(
probability of 1 ) t . Therefore, we can write:
t t t t
C avg (n) = .1[  . 2  .....  . i  ....  . n ] n .( 1 ) t
n n n n
t
= 1 [  2  i ...  ...  ] n  i ( n  ) t
n
t n ( n  ) 2
=  1 ( n  ) t
n 2
n ( t  ) 1
=  1 ( n  ) t
2
For t=1, the average number of key comparisons made by sequential search is
n (  ) 1
which means the algorithm inspects on an average about half of the
2

LOVELY PROFESSIONAL UNIVERSITY 33