Page 564 - Computer science 868 Class 12
P. 564
The complexity calculation is some what similar to Bubble Sort.
In the first pass, j loop executes (n-1) times.
In the second pass, j loop executes (n-2) times.
In this way, the j loop executes 1 time in the last pass.
Thus, total number of steps executed is
(n-1)+(n-2)+(n-3).......+2+1
= n(n-1)/2
2
= n /2 - n/2
2
2
The dominant term being N is considered. So, the complexity of Selection Sort is O(N ).
Insertion Sort: The algorithm for insertion sort is given below.
for (int i = 1; i < n; ++i)
{
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key;
}
}
Total number of times the loop executed is: 1+2+3+....+(n-1)
= n*(n-1)/2
= n /2 - n/2
2
2
2
The dominant term being N is considered. So, the complexity of Insertion Sort is O(N ).
The best case complexity where the data is already sorted is O(N).
The worst and average case complexity is O(N ).
2
Let’s Revisit
♦ The effectiveness of an algorithm is depicted by how accurately it produces a result.
♦ An efficient algorithm is one which produces accurate result in minimum time using minimum resources.
♦ Computation involves the process of solving a problem and the algorithm associated with it. Complexity involves the study of
factors like time taken by an algorithm and space utilised by it to determine the minimum resource requirement. Complexity
is thus the measurement of the performance of an algorithm.
♦ Space complexity is the amount of memory space required to run an algorithm. An algorithm which requires the least memory
is considered more efficient.
♦ Time complexity is the total time taken to execute the instructions (steps) of a program. An algorithm which is designed using
the least number of steps is considered more efficient.
562562 Touchpad Computer Science-XII

