GATE 2013
April 5, 2025GATE 2013
April 5, 2025GATE 2013
| Question 31 |
The number of elements that can be sorted in Θ(log n) time using heap sort is
| Θ(1) | |
| Θ(√logn) | |
| Θ (logn/loglogn) | |
| Θ(log n) |
Question 31 Explanation:
Using heap sort to n elements it will take O(n log n) time. Assume there are log n/ log log n elements in the heap.
So, Θ((logn/ log log n)log(logn/log log n))
= Θ(logn/log logn (log logn – log log logn))
= Θ((log n/log logn) × log log n)
= Θ(log n)
Hence, option (C) is correct answer.
So, Θ((logn/ log log n)log(logn/log log n))
= Θ(logn/log logn (log logn – log log logn))
= Θ((log n/log logn) × log log n)
= Θ(log n)
Hence, option (C) is correct answer.
Correct Answer: C
Question 31 Explanation:
Using heap sort to n elements it will take O(n log n) time. Assume there are log n/ log log n elements in the heap.
So, Θ((logn/ log log n)log(logn/log log n))
= Θ(logn/log logn (log logn – log log logn))
= Θ((log n/log logn) × log log n)
= Θ(log n)
Hence, option (C) is correct answer.
So, Θ((logn/ log log n)log(logn/log log n))
= Θ(logn/log logn (log logn – log log logn))
= Θ((log n/log logn) × log log n)
= Θ(log n)
Hence, option (C) is correct answer.