Description
Using Figure 6.4 (Textbook, Exercise 6.4-1) as a model, illustrate the operation of HEAPSORT on the array A={5, 12, 2, 25, 7, 17, 20, 8, 14} and output the numbers in a non-decreasing order. (Write your result of each step.)
- Max-Min Problem: find the maximum and the minimum numbers of a sequence number in a divide-and-conquer manner. (Let 𝑛 be the size of the sequence. For simplicity, assume that 𝑛 = 2!.)
- (40 points) How to do it? Please write the pseudo-code of your algorithm.
- (20 points) What is time complexity of your algorithm? Please present analysis process.
- (20 points) Give asymptotic upper bound (represented by O( )) of the recursive function T(n) = T(n-2) + n. Assume that T(n) is constant for n£2.
1
