Algorithms
October 23, 2023DigitalLogicDesign
October 23, 2023Arrays
Question 52

θ(n)


θ(lgn)


θ(nlgn)


θ(n^{2})

inversions in input permutation a1,a2,…an. Since for each value of i=1..n, j take the value 1..i−1, which means for every j < i it checks if a [ j ] > a [ i ] .
→ In any given permutation, maximum number of inversions possible is n(n1)/2 which is O(n^{2}). It is the case where the array is sorted in reverse order.
→ To resolve all inversions i.e., worst case time complexity of insertion sort is Θ(n^{2}).
→ However, as per the question the number of inversions in input array is restricted to n.
→ The worst case time complexity of insertion sort reduces to Θ(n).
inversions in input permutation a1,a2,…an. Since for each value of i=1..n, j take the value 1..i−1, which means for every j < i it checks if a [ j ] > a [ i ] .
→ In any given permutation, maximum number of inversions possible is n(n1)/2 which is O(n^{2}). It is the case where the array is sorted in reverse order.
→ To resolve all inversions i.e., worst case time complexity of insertion sort is Θ(n^{2}).
→ However, as per the question the number of inversions in input array is restricted to n.
→ The worst case time complexity of insertion sort reduces to Θ(n).