Skip to content
GATETECH
Official PYQ · 2015Set 3 · Q27Searching, Sorting, HashingMCQ1 mark

GATE CS 2015 Set 3 Q27 — Searching, Sorting, Hashing

Explain with AI

Assume that a mergesort algorithm in the worst case takes 3030 seconds for an input of size 6464. Which of the following most closely approximates the maximum input size of a problem that can be solved in 66 minutes?

Choose one option
View worked solution

Answer: B

The worst-case time complexity of the Mergesort algorithm for an input of size NN is given by:

T(N)=c⋅Nlog⁡2NT(N) = c \cdot N \log_2 N

where cc is a constant.

Step 1: Determine the constant cc

We are given that for N=64N = 64, the time taken is 3030 seconds:

T(64)=c⋅64log⁡2(64)=30T(64) = c \cdot 64 \log_2(64) = 30 c⋅64⋅6=30c \cdot 64 \cdot 6 = 30 384c=30  ⟹  c=30384=564384c = 30 \implies c = \frac{30}{384} = \frac{5}{64}

Step 2: Find the maximum input size MM for 66 minutes

We want to find the maximum input size MM that can be solved in 66 minutes (6×60=3606 \times 60 = 360 seconds):

T(M)≤360T(M) \le 360 c⋅Mlog⁡2M≤360c \cdot M \log_2 M \le 360 564⋅Mlog⁡2M≤360\frac{5}{64} \cdot M \log_2 M \le 360 Mlog⁡2M≤360×645M \log_2 M \le \frac{360 \times 64}{5} Mlog⁡2M≤72×64M \log_2 M \le 72 \times 64 Mlog⁡2M≤4608M \log_2 M \le 4608

Step 3: Test the given options

  • Option A (M=256M = 256):
    256log⁡2(256)=256×8=2048≤4608256 \log_2(256) = 256 \times 8 = 2048 \le 4608 (Feasible, but we need the maximum size)
  • Option B (M=512M = 512):
    512log⁡2(512)=512×9=4608≤4608512 \log_2(512) = 512 \times 9 = 4608 \le 4608 (Exactly matches the limit)
  • Option C (M=1024M = 1024):
    1024log⁡2(1024)=1024×10=10240>46081024 \log_2(1024) = 1024 \times 10 = 10240 > 4608 (Exceeds the limit)

Thus, the maximum input size that can be solved in 66 minutes is 512512.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Searching, Sorting, Hashing questions