Relation between running time of insertion sort and number of inversions in an array
  • mergesort
  • sorting
  • noofinversion
  • insertionsort
  • timecomplexity
  • array
  •   
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (8846)

Suppose you are applying insertion sort on an array. How will you relate its running time with the number of inversions?


Posted Answers

An inversion in an array a[ ] is a pair of entries a[i] and a[j] such that i < j and a[i] > a[j] . The number of inversions w.r.t the current element, a[i] , is \( c_i-1 \), at each iteration, where \( c_i \) is the number of comparisons. If the total number of inversions ( Counting Inversions problem ) is \( N_i \), running time of insertion sort is \( O(n+N_i) \).

You need to Sign In to post your solution.