Consider the Triple Search algorithm for searching in a sort

Consider the Triple Search algorithm for searching in a sorted array A[0..N-1]:

If N==1, compare the searched-for key K with A[0].

Otherwise compare K with A[n/3] and, if K is larger, with A[2n/3] to determine in which third of the array to continue the search.

Questions

Set up and solve the recurrence for N = 3^k

Solution

We know A is sorted. The process is we are dividing A in to three equal parts to reduce the search size. Assume N=3k. We compare K with A[0] is it less then K is not present in A. Otherwise we compare with A[k-1], if it is less then we recuse with subarry A[0-k]. Otherwise we check with A[2k-1], if it less we recurse with A[k..2k-1], otherwise we recurse with A[2k..3k-1].

The time taken will be

T(n) = T(n/3) + O(1)

Next we get T(n/3) = T(n/9) + O(1) then T(n/9) = T(n/27)+O(1).

extending like wise until T(3) = T(1)+O(1)

Adding all of them we get T(n) = T(1)+(log(3)n)*O(1)

We know T(1)=O(1).

So T(n) = O(log(3)n)