Answer to Question heapsort-6

1. In the worst case, the loop needs to go through n−1 times. The loop body involves a constant amount of work. So the time is Θ(n) in the worst case.

2. insert(A,k) takes time propotional to k. So the time used for the loop is c(1 + 2 + ... (n−1)) for some constant c. That is c(n)(n−1)/2, which is Θ(n²).

3. Heapsort is much faster. Its time is Θ(nlog₂(n)).