GATE 1992
April 18, 2024Question 10618 – Sorting
April 18, 2024Question 10667 – Sorting
If we use Radix Sort to sort n integers in the range [nk/2, nk], for some k>0 which is independent of n, the time taken would be?
Correct Answer: C
Question 14 Explanation:
Time complexity for radix sort = Θ(wn)
where n = keys, w = word size
w = log2 (nk) = k × log2 (n)
Complexity Θ(wn) = Θ(k × log2(n) × n) = Θ(n log n)
= Θ(n log n)
where n = keys, w = word size
w = log2 (nk) = k × log2 (n)
Complexity Θ(wn) = Θ(k × log2(n) × n) = Θ(n log n)
= Θ(n log n)
Θ(n)
Θ(kn)
Θ(nlogn)
Θ(n2)