PUERTA | GATE-CS-2015 (Conjunto 3) | Pregunta 37

Suponga que un algoritmo mergesort en el peor de los casos tarda 30 segundos para una entrada de tamaño 64. ¿Cuál de los siguientes se aproxima más al tamaño máximo de entrada de un problema que se puede resolver en 6 minutos?
(A) 256
(B) 512
(C) 1024
(D) 2048

Respuesta: (B)
Explicación:

Time complexity of merge sort is Θ(nLogn)

c*64Log64 is 30
c*64*6 is 30
c is 5/64

For time 6 minutes

5/64*nLogn = 6*60

nLogn = 72*64 = 512 * 9

n = 512. 

Cuestionario de esta pregunta