Assume that a merge sort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

GATE : Computer Science and IT

Assume that a merge sort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

A. 256

B. 512

C. 1024

D. 2048

Solution

B. 512

Explanation

Time complexity of merge sort is Θ (n Log n)
c * 64Log64 is 30
c * 64 * 6 is 30
c is 5/64
For time 6 minutes
5/64* n Log n = 6*60
n Log n = 72*64 = 512 * 9
n = 512