Homework 7

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

## Reviews

There are no reviews yet.