Home › Previous year questions › GATE 2013 CS (CS1) › Question 40GATE 2013 CS (CS1) – Question 40 Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice
How many elements can heap sort sort in $\Theta(\log n)$ time?
$\Theta(1)$ $\Theta(\sqrt{\log n})$ $\Theta(\log n/\log\log n)$ $\Theta(\log n)$ Practise this question in The GATE Grind →
Show answer and explanation Correct answer: (C) $\Theta(\log n/\log\log n)$
Explanation Heap sorting m elements takes Θ(m log m). Choose $m=\Theta(\log n/\log\log n)$; then log m=Θ(log log n), and their product is Θ(log n). Thus C. Sorting Θ(log n) elements would add a log log n factor.
More Asymptotic Analysis and Time/Space Complexity questions GATE 2013 CS (CS1) Q41 – What is the asymptotic return value, rather than running time? GATE 2011 CS (CS1) Q47 – Find increasing asymptotic growth order for f 1(n)=2n, f 2(n)=n3/2, f 3(n)=n 2n, f 4(n)=n… GATE 2010 CS (CS1) Q22 – Packages A,B process n=10k database records. A needs 0.0001n² time; B needs 10n 10n. Find… GATE 2015 CS (CS2) Q16 – An unordered list contains n distinct elements. How many comparisons are needed to find… GATE 2015 CS (CS2) Q26 – Decision problem Q1 reduces in polynomial time to 3-SAT, and 3-SAT reduces in polynomial… GATE 2015 CS (CS3) Q20 – For i=0n i3=X, consider I (n4), II (n5), III O(n5), IV (n3). Which may replace X? All Asymptotic Analysis and Time/Space Complexity questions →