Question 10 (10 marks] Consider the non-recursively defined function below for integers n > 0. Write a recursive version of this function and show that the two versions are defining the same function. f(n) = a 61 (2) Question 11 (10 marks] Recall that in MergeSort, we divide a list L of size n into two lists L and L2 of size n/2, we sort L and L2 recursively, and then merge the sorted L and L2. Consider a variant of MergeSort, called MergeSort Var, where we divide a list L of size n = 3k, for some non-negative integer k, into three lists L1, L2, and L3 of size n/3, we sort L1, L2, and L3 resursively (using MergeSort Var), and then merge the sorted L1, L2, and L3. Assume the merge operation (of L1, L2, and L3) can be done by using n comparison operations. What is the time complexity of MergeSort Var? Question 12 [10 marks] Consider a set S defined recursively in the following way: les If n ES then 2n ES. Show that every non-negative integer power of 2 is in S (i.e. In > 0,2" ES)