Consider the following alteration to the binary search algorithm. Note that a[i:j] denotes a slice

of the array from index i to index j, inclusive.

Algorithm trinarySearch(a, num):

Input: an array a of n sorted integers and an integer num

Output: the index of num in the array or -1 if num does not appear in the array

if(a.length < 2)

return -1

i1 := floor[n/3]

i2 := floor[2n/3]

if(num == a[i1])

return i1

if(num == a[i2])

return i2

if(num < a[i1])

trinarySearch(a[0:i1])

else if(num < a[i2])

trinarySearch(a[i1+1:i2])

else

trinarySearch(a[i2+1:n-1])

Write and explain a recurrence relation for the runtime of this algorithm. Then use the

formal definition of big-Oh and induction to prove a tight upper bound for the runtime.

Hint: log is base 3, and You may want to prove specifically that () N + 1 for all 1 and

some constant > 0, which is acceptable since + 1 is ().