You are given n sorted sequences each one containing n keys. You may assume n is a power of two. We want to merge them into one sorted sequence containing all the keys. Assume all of the keys are distince. What is an upper bound on the number of comparisons performed. Provide a multiplicative constant for the most important number and as much as possible for the remaining terms. (Only the result counts.)

Question

Computers and Technology

Esmeralda Pierce

25 July, 08:59

You are given n sorted sequences each one containing n keys. You may assume n is a power of two. We want to merge them into one sorted sequence containing all the keys. Assume all of the keys are distince. What is an upper bound on the number of comparisons performed. Provide a multiplicative constant for the most important number and as much as possible for the remaining terms. (Only the result counts.)

+2

Answers (1)

Know the Answer?

Jaime Conrad · Answer 1

Upper bound means the algorithm will not use more time than this.

Since there n sorted sequence and having n distinct keys, the upper bound will be:

O (n^2logn) using Min Heap, n^2 because there will be the output of array size n*n