a) In the worst case, how many comparisons does the insertion sort algorithm use

Question

a) In the worst case, how many comparisons does the insertion sort algorithm use to sort n items? Please explain your reasoning, and please do NOT use big-O notation.

b) Using answer from the previous question to give a big-O estimate of the worst case complexity of the insertion sort in terms of the number of comparisons for the insertion sort.

c) Give a big-O estimate of the worst case complexity of binary insertion sort in terms of the number of comparisons for the binary insertion sort.

d) In worst case, how many terms are swapped by the binary insertion sort algorithm to sort n items? Please exlain reasoning, and please do NOT use big-O notation

Explanation / Answer

a) it takes n number of comparisions to sort the elements without big O estimate.

b) for the worst case, it can be sorted using an array in reverse manner.each and every iteration of inner loop will scan before inserting the next element. In this case, number of comparisions will be O(n2)

c) for binary insertion sort, the worst case is O(n2), as it takes number of swaps for each insertion of elements

d) based on the given set of elements, without big O notation, for each insertion, number of swaps will be done in the program

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.