The worst case performance in insertion sort occurs when the elements of the input array are in descending order. In that case, the first pass requires one comparison, the second pass requires two comparisons, third pass three comparisons,….kth pass requires (k-1), and finally the last pass requires (n-1) comparisons. Therefore, total numbers of comparisons are:
f(n) = 1+2+3+………+(n–k)+…..+(n-2)+(n-1) = n(n-1)/2 = O(n2)
