Below is the mystery algorithm that we worked 011 in Problem

Below is the mystery algorithm that we worked 011 in Problem Set 4. def mystery(1st): if len (1st) 1st[-1]: 1st [0], 1st[-1] = 1st[-1], 1st [0] if len (1st) > = 3: split = len(1st)//3 mystery(1st [0..len(1st) - split - 1]) mystery(1st[split..1en(1st) - 1]) mystery(1st [0..1en(1st) - split - 1]) We analyzed that the recurrence of the worst-case runtime of this algorithm is the following. T(n) = {C, if n lessthanorequalto 2 3T(2n/3) + d, if n greaterthanorequalto 3 Some students have already realized that this algorithm is in fact a sorting algorithm. So in this problem set we will formalize our understanding of this interesting sorting algorithm. (a) Find the asymptotic upper-bound on the worst-case runtime of mystery using the master theorem. State clearly which case of the master theorem applies. (b) State the proper precondition and postcondition for the mystery function. (c) Prove that mystery is correct according to the precondition and postcondition that you specified in (b).

Solution

1) This type of recurrences can be solved with a Master theorem. Here a=3, b=3/2 and f(n) = 1. Your c = log1.5(3) = 2.709 And because n^2.709 is bigger than f(n), you fall into first case.

So the solution is O(n^2.709)

2) The list should be either a list of numbers or alphabets and not both. No duplicates should be present.