Page 37 - DCAP407_DATA_STRUCTURE

Data Structure

Table 2.2 shows the analysis of time complexity.

Table 2.2: Analysis of Time Complexity

Algorithm Step Statements/Instructions
A x = x+1
for a = 1 to n step 1
B x = x+1
Loop
for a = 1 to n step 1
for b = 1 to n step 1
C
x = x+1
Loop

In the table 2.2:

1. In step A, there is one independent statement ‘x= x+1’ and it is not within any loop. Hence, this
statement will be executed only once. Thus, the frequency count of step A of the algorithm is 1.
2. In step B, there are three statements out of which ‘x = x+1’ is an important statement. As the
statement ‘x = x+1’ is contained within the loop, the statement will be executed n number of times.
Thus, the frequency count of algorithm is n.
3. In step C, the inner and outer loop runs n number of times. Thus, the frequency count is n 2 .
During the analysis of algorithm, the focus is on determining those statements that provide the greatest
frequency count. The formulas used to calculate the steps executed by an algorithm are:
1 + 2 +……+ n = n(n+1)/2
1 2 +2 2 +…..+ n 2 = n(n+1)(2n+1)/6
If an algorithm has input of size n and performs f(n) basic functions, then the time taken to execute
those functions will be cf(n), where c is a constant that depends upon the algorithm design.

The time complexity of an algorithm can be further analyzed as best case, worst case and average case
time complexity.
1. In best case time complexity, an algorithm will take minimum amount of time to solve a particular
problem. In other words, the algorithm runs for a short time.

Bubble sort has a best case time complexity of n.

2. In worst case time complexity, an algorithm will take maximum amount of time to solve a
particular problem. In other words, algorithm runs for a long time.

Quicksort has a worst case time complexity of n 2 .

3. In average case time complexity, only certain sets of inputs to the algorithm get the time
complexity. It specifies the behavior of an algorithm on a particular input.

30 LOVELY PROFESSIONAL UNIVERSITY