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.