GATE 2015 CS (CS3) – Question 37

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

Worst-case mergesort takes 30 seconds for input size 64. Which best approximates the maximum size sortable in six minutes?

256
512
1024
2048

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) 512

Explanation

Model time as c n log₂n. Six minutes is twelve times thirty seconds, so the target n log₂n is 12×64×6=4608. At n=512, n log₂n=512×9=4608 exactly. Thus B is the matching size under the stated asymptotic model.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2015 CS (CS3) Q41 – L1≤pL2, L3≤pL2 and L2≤pL4. Which are guaranteed? I: L4∈P implies L2∈P. II: L1∈P or L3∈P…
GATE 2015 CS (CS3) Q64 – For positive integer n, f(n)=n and g(n)=n1+ n. Which hold? I: f=O(g). II: f=Ω(g).
GATE 2021 CS (CS2) Q49 – For constants a≥1,b>1, T(n)=aT(n/b)+f(n). Which general claim is correct, under the usual…
GATE 2026 CS (CS1) Q17 – Consider the following recurrence relations: For all n > 1: T 1(n) = 4T 1(n/2) + T 2(n) T…
GATE 2026 CS (CS1) Q47 – Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset V' V such that…
GATE 2026 CS (CS2) Q24 – Consider the following functions, where n is a positive integer: n1/3, n, (n!), and 2 n.…

All Asymptotic Analysis and Time/Space Complexity questions →