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

Vito

Computers & Technology

12 September, 04:07

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.)

+4

Answers (1)

Know the Answer?

Danica Blackwell · 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