3. Consider the following recursive algorithm: Preconditions: A is an array of integers. f and are integers such that Osfs (e- f +1)/2: 12 return r 13 eturn maj(A, m +1,e) (a) Let T(n) denote the worst-case running time of the algorithm below on inputs of size n. Write a recurrence relation satisfied by T. Then, give an asymptotic upper-bound for the worst-case running time of the algorithm. Make sure to define n precisely and justify that your recurrence is correct by referring to the algorithm to describe how you obtained each term in your answer For this part of the question (and only this part), you may assume that len(Af:1]) and len(A) are powers of 2 (b) State an invariant for the loop on line 7 that describes the value of c at the end of every iteration of the loop Prove your loop invariant c) Prove the correctness of maj with respect to the given specification Use induction for the correctness proof and follow the steps (i)-(iv) below You may assume that the loop on line 7 terminates without proof Also, you may use the following fact without proof If u , +1 w, and b occurs more than s+s' times in Bu:w 1], then either b occurs more than s times in Buv+1] or b occurs more than s' times in Blv+1w+1] (Recall that Bij is the slice of B from i to j) i. Define a predicate P(k) that denotes the correctness of maj for an input with size k ii. Prove the base case iii. State the induction hypothesis. iv. Prove the induction step 3. Consider the following recursive algorithm: Preconditions: A is an array of integers. f and are integers such that Osfs (e- f +1)/2: 12 return r 13 eturn maj(A, m +1,e) (a) Let T(n) denote the worst-case running time of the algorithm below on inputs of size n. Write a recurrence relation satisfied by T. Then, give an asymptotic upper-bound for the worst-case running time of the algorithm. Make sure to define n precisely and justify that your recurrence is correct by referring to the algorithm to describe how you obtained each term in your answer For this part of the question (and only this part), you may assume that len(Af:1]) and len(A) are powers of 2 (b) State an invariant for the loop on line 7 that describes the value of c at the end of every iteration of the loop Prove your loop invariant c) Prove the correctness of maj with respect to the given specification Use induction for the correctness proof and follow the steps (i)-(iv) below You may assume that the loop on line 7 terminates without proof Also, you may use the following fact without proof If u , +1 w, and b occurs more than s+s' times in Bu:w 1], then either b occurs more than s times in Buv+1] or b occurs more than s' times in Blv+1w+1] (Recall that Bij is the slice of B from i to j) i. Define a predicate P(k) that denotes the correctness of maj for an input with size k ii. Prove the base case iii. State the induction hypothesis. iv. Prove the induction step