# Recurrence for quaternary search algorithm

I have to come up with the recurrence for the quaternary search algorithm.

My initial thought is $T(n)=4T(\frac{n}{4})+c$ because the algorithm examines all four subproblems, and each is one quarter the size of the entire array. But this can't be right because that yields a complexity of $O(n)$. I looked on Google and the complexity of quaternary searches are supposed to be $\log_4n$, but I don't know what the recurrence would be to get me that complexity.

Any help would be greatly appreciated. Thanks!

Moreover, as mentioned in the comments, the running time (assuming constant-time comparisons and the RAM machine model) is $\Theta(\log n)$, but cannot get more accurate than that. To get $\log_4 n$ you need to count something more specific, such as the number of comparisons performed by the algorithm.
The correct recursion formula is $T(n) = T(\frac{n}{4}) + c$, which yields $O(lgn)$. Because the base is 4 here, for quaternary searches it becomes $O(log_4n)$.