consider the following modification to the mergesort algorithm divide the input arra 3599203

Question 1 [4 points]

Express the following function in terms of Big-oh notation:

1. (n

3

)/1000 – 100 * n

2 + 50

2. n

a + n

b

(a > b and b > 0)

Question 2 [10 points]

Consider the following modification to the MergeSort algorithm: divide the input array into thirds (rather than halves), recursively sort each third, and finally

combine the results using a three-way Merge subroutine. What is the running

time of this algorithm as a function of the length n of the input array, ignoring

the constant factors and lowest order terms ? [Hint: the Merge subroutine can

still be implemented so that the number of operations is only linear in the sum

of the input array length.]

Question 3 [10 points]

Suppose you are given k sorted arrays, each with n elements, and you want to

combine them into a single array of kn elements. Our approach is to use the

linear time Merge subroutine [O(n) runtime] repeatedly, first merging the first

two arrays, then merging the result with the third array, then with the fourth

array, and so on until you merge in the k-th and the final input array. What is

the running time taken by this successive merging algorithm, as a function of k

and n, ignoring constant factors and lower-order terms.

Question 4 [10 points]

Consider again the problem if merging k sorted length-n arrays into a single

sorted length-kn array. Consider the algorithm that first divides the k arrays

into k/2 pairs of arrays, and use the merge subroutine to combine each pair,

resulting in k/2 sorted length-2n arrays, The algorithm repeats this step until

there is only one length-kn sorted array. What is the running time taken by

this successive merging algorithm, as a function of k and n, ignoring constant

Attachments:

Assignment-1.pdf