Sublists

6. 20pts) Consider the following extension to binary search on a sorted array A for an ite x: Let A[p] and Alal 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 sublists but no more). Based on Alpl and Ala), decide the sublist where x may exist. Repeat this process until the sublist is small enough that the answer can be directly obtained. .Write pseudo-code for the above TernarySearch method, specifying all the parameters correctly. . Derive the recurrence relation for the running time of the TernarySearch algorithm. .Solve the recurrence relation, find a close-bound for the running time of TernarySearch and then express this close-bound using asymptotic notation. Justify your answer. Derive an expression and its asymptotic bound for the space complexity of . TernarySearch