Consider the following extension to binary search on a sorted array A for an item x: Let A[p] and A[q] be the partitioning elements of A so that A is divided into three roughly equal-sized lists (i. e., a difference of 1 or 2 is allowed between the sizes of these sub-lists but no more). Based on A[p] and A[q], decide the sub-list where x may exist. Repeat this process until the sub-list is small enough that the answer can be directly obtained. 1. Write pseudo-code for the above Ternary-Search method, specifying all the parameters correctly.
2. Derive the recurrence relation for the running time of the Ternary-Search algorithm.
3. Solve the recurrence relation, find a close-bound for the running time of the Ternary-Search and then express this close-bound using asymptotic notation.
4. Derive an expression and its asymptotic bound for the space complexity of the Ternary-Search.