Thomas thinks that he might improve on binary search of sorted array A: he will divide the array's elements in thirds instead of halves, recursing, when necessary, on the correct third.
(a) Write pseudocode for algorithm TS that correctly captures the idea of this trinary search."
(b) Write down a recurrence relation that gives, precisely, the worst-case number of comparissons used by TS.
(c) Write down a recurrence relation that gives, within a constant, the anticipated worst-case running time of TS.
(d) Solve this recurrence relation to within ().