Consider mergesort when the number of keys, n, is not a power of 2. a) The...

Transcribed Image Text:

Consider mergesort when the number of keys, n, is not a power of 2. a) The recursion tree will split a problem of size m into problems of size [m/2] and [m/2]. Using induction, show that the problem sizes on a level of the recursion tree (except for possibly the final level) are within 1 of each other. b) Counting the first level as 0, what is the number of the last full level? c) Conclude that the worst-case number of comparisons for merge sort is (as was claimed) Consider mergesort when the number of keys, n, is not a power of 2. a) The recursion tree will split a problem of size m into problems of size [m/2] and [m/2]. Using induction, show that the problem sizes on a level of the recursion tree (except for possibly the final level) are within 1 of each other. b) Counting the first level as 0, what is the number of the last full level? c) Conclude that the worst-case number of comparisons for merge sort is (as was claimed)

Answer rating: 100% (QA)

The image you provided presents a problem statement related to the analysis of the merge sort algori... View the full answer