CMSC351 Kruskal Homework 1 Due Friday February 14 2025 1 Consider a list where you know that the value of every item is within the middle third of the values that are above it More formally the value of the ith element is somewhere between the i 3 to 2i 3 largest of the rst i elements You will modify insertion sort with a sentinel to take advantage of this fact In order to avoid worrying about oors and ceilings the exact de nition of middle third is up to you and can be de ned implicitly by your program For the following analyses just get the EXACT high order term Justify your answers a Brie y explain your modi cation in English b Write pseudo code for your algorithm c How many comparisons does your algorithm do in the best case d How many comparisons does your algorithm do in the worst case e How many comparisons does your algorithm do in the average case f How many moves does your algorithm do in the best case g How many moves does your algorithm do in the worst case h How many moves does your algorithm do in the average case
View Full Document
Unlocking...