GATE CS 2015 Set 3 Q.37 (CS Q.27): Searching and Sorting Algorithms

Assume that a mergesort 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?

256

512

1024

2048

Official answer and solution

Official answer: B
From: Official GATE 2015 answer key

Solution

Use the asymptotic complexity T(n) = c * n * log2(n) of mergesort to determine the maximum input size solvable in 6 minutes.

The worst-case running time of mergesort for input size $n$ is given by:

T(n) = c \cdot n \log_2 n

Given $T(64) = 30\text{ seconds}$ :

30 = c \cdot 64 \cdot \log_2(64) = c \cdot 64 \cdot 6 = 384 c \implies c = \frac{30}{384} = \frac{5}{64}

The available time is 6 minutes $= 6 \times 60 = 360\text{ seconds}$ . We solve for $n$ :

\frac{5}{64} \cdot n \log_2 n = 360 \implies n \log_2 n = \frac{360 \times 64}{5} = 72 \times 64 = 4608

Test the candidate input sizes:

$n = 256$ : $256 \log_2(256) = 256 \times 8 = 2048$
$n = 512$ : $512 \log_2(512) = 512 \times 9 = 4608$
$n = 1024$ : $1024 \log_2(1024) = 1024 \times 10 = 10240$
For $n = 512$ , $n \log_2 n = 4608$ matches the available time exactly.

Final answer

Common trap

Assuming linear scaling (64 * (360/30) = 768) and ignoring the n log n factor.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 3
Question: 37 of 65, printed as CS Q.27
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source