Question

What is the best-case time for Heapsort to sort an array of n records that each have unique key values?

a. Θ(logn)
b. Θ(n²)
c. Θ(nlogn)
d. Θ(n)
e. Θ(n^n)

Answer 1

The best-case time for Heapsort to sort an array of n records with unique key values is Θ(nlogn).

Step-by-step explanation:

The best-case time for Heapsort to sort an array of n records with unique key values is Θ(nlogn). In Heapsort, the array is first transformed into a heap, which takes Θ(n) time. Then, the heap is repeatedly modified to ensure the largest element is at the root and swapped with the last element, which takes logn time. This process is repeated for each element in the array, resulting in a total time complexity of Θ(nlogn).