Quiz on sorting

#1

I am not able to understand this question can you please explain the question along with answer:
In a permutation a1……an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1……n with at most n inversions?

#2

Hello @radhika1995,

As the question says, how the Inversion is defined.

In a permutation a1…an, of n distinct integers, an inversion is a pair (ai,aj) such that iaj.

  • One important thing to see is Difference between swap and Inversions.
  • Swapping is done explicitly by the programmer, hence an explicit feature whereas, Inversion is an implicit feature which is defined in the input.

Ex :- Take the input => {0,1,9,8,10,7,6,11}
How many Inversions here : {9,8} , {9,7} , {9,6} ,{8,7} , {8,6} , {10,7} and {10,6}. Hence, it is an implicit feature of the input and not any explicit operation done (Swap) .

The actual Time complexity of Insertion Sort is defined as Θ(N+f(N)), where f(N) is the total number of Inversions.

Ex :- Again take the input => {0,6,7,8,9,10,1}
Here, how many comparisons will be there to place 1 in the right place ?

  • First of all, 1 is compared with 10 - Returns True as it is smaller than 10.
  • Then, with 9 - again True.
  • Similar, happens with 6,7,8 - All return True.

Hence, There 5 comparisons were the Inversions and 1 more comparison will be there, in which outer while loop fails.

For, placing 1 in the right place 6 comparisons are there.

Hence, Total Comparisons in the Insertion sort will be:- Total number of elements for which our while loop fails + Total number of inversions in the input

  • Total number of elements for which our while loop fails :- Suppose the input {0,6,7,8,9,10,1}. Here, first 0 will be kept as it is and one while loop fails the comparison for each element, hence total comparisons like this:-
    (N−1)=O(N) comparisons.
  • the total number of inversions in the input:- Best Case : 0 and in the Worst Case :
    N(N−1)/2=O(N^2)

The total Time complexity of insertion sort: Θ(N+f(N))

It is given here that at most N inversions are there, so we get the best Time complexity:- Θ(N+f(N))=Θ(N+N)=Θ(N).

Hope, this would help.
Give a like if you are satisfied.