COT 4400 Homework 7 solution

Description

1. Find a recurrence T(n) that describes the runtime of the RecursionMystery algorithm below:
Input: data: array of integers
Input: n: size of data
1 Algorithm: RecursionMystery
2 if n > 1 then
3 min = max = 1
4 for i = 2 to n do
5 if data[i] < data[min] then 6 min = i 7 end 8 if data[i] > data[max] then
9 max = i
10 end
11 end
12 Swap data[1] and data[min]
13 if max > 1 then
14 Swap data[n] and data[max]
15 else
16 Swap data[min] and data[max]
17 end
18 if n > 2 then
19 Call RecursionMystery on data[2..n − 1]
20 end
21 end
22 return data
2. Draw the recurrence tree that corresponds to the recurrence T(n) =
4T(n/2) + Θ(1).
1