Page 41 - DCAP407_DATA_STRUCTURE

Data Structure

list’s elements.
For t=0, the average number of key comparisons is n which means the
algorithm inspects all n element on all such inputs.

The investigation of average case efficiency is more difficult compared to the best case
efficiency and worst case efficiency. The direct approach for computing the average
case efficiency involves the divison of all instances of size n into several classes. Thus,
for each instance of the class, the number of times the algorithm’s basic operation
executed is same.
Worst Case Analysis

If an algorithm takes maximum amount of time to execute for a specific set of input, then it is called the
worst case time complexity. The worst case efficiency of an algorithm is the efficiency for the worst case
input of size n. The algorithm runs the longest among all the possible inputs of the similar size because
of this input of size n.
To determine the worst case efficiency of an algorithm, we have to analyze the algorithm to identify the
kind of input suitable for the largest value of the basic operation’s count C(n) among all possible inputs
of size n. Then, we can compute the worst case value C worst(n).

In case of sequential search, if the search element key is present at the n position
th
of the list, then the basic operations and time required to execute the algorithm is
more. Thus, it gives the worst case time complexity. Worst case time complexity
is represented as:
Cworst(n)=n

Worst case efficiency guarantees that for any instance of size n, the running time will not exceed
C worst(n), the running time on the worst-case inputs.
2.4 Summary

• A computer program is written as a sequence of steps that needs to be performed to obtain the
desired result.
• Mathematical notation is a system of symbolic representations of mathematical objects and ideas.
• Some of the mathematical functions are floor and ceiling functions, summation symbol, factorial,
Fibonacci numbers, and so on.
• The complexity of an algorithm is a function which describes the efficiency of an algorithm in
terms of the amount of data the algorithm must process.
• The efficiency of each algorithm can be checked by computing its time complexity.

• The asymptotic notations help to represent the time complexity in a shorthand way. It can
generally be represented as fastest possible, slowest possible, or average possible.
• The floor and ceiling functions give the nearest integer up or down.
• In the Fibonacci sequence, after the first two numbers, i.e., 0 and 1 in the sequence, each
subsequent number in the series is equal to the sum of the previous two numbers.
• Analysis of an algorithm is required to determine the amount of resources such as, time and
storage required to execute the algorithm.

34 LOVELY PROFESSIONAL UNIVERSITY