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 I examine all 4 subproblems, and each is 1/4 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!

The correct recursion formula is $T(n)=T(\frac{n}{4})+cT(n)=T(n4)+c$, which yields $O(lgn)$. Because the base is 4 here, for quaternary searches it becomes $O(log_4n)$.