# Time complexity of an uneven binary search

I have a concept binary search which doesn't split at the midpoint of a list, but at a ratio of 1:2.

If we abstract the search function time complexity into $$T(n)$$ then the function can recurse into two options:

• $$T(n/3) + C(n)$$
• $$T(2n/3) + C(n)$$

I am unable to understand how to properly find this time complexity using the methods I've learned so far, which doesn't include randomization or means or whatnot. I have been taught the master method, iteration method and perturbation method.

I was thinking that I just take the worst case, i.e. $$T(2n/3) + C(n)$$ and use that with the methods I know, but I don't feel like this would work for finding $$\Theta(n)$$ i.e. the tightest bound, but rather only for the upper bound. Would it be possible to find $$\Theta(n)$$ using the information given?

• What's $C(n)$? Is it $O(n)$? But yes, looking at the worst case in each split will give you the general worst-case complexity. Commented Oct 27, 2023 at 3:25
• $C(n)$ is just a general addition to the recursion that each recursion level does in splitting/joining the results back together. In the case of the binary search, it's $C(n) = 1$ I believe Commented Oct 27, 2023 at 3:29
• The solution depends on $C(n)$. If $C(n) = O(1)$ then it's $T(n) = O(\log n)$. Commented Oct 27, 2023 at 3:29
• I'm reasonably confident in saying that for $\mathcal{O}(n)$ but I was unsure about the $\Theta(n)$ complexity Commented Oct 27, 2023 at 3:31

We have $$T(n) = \max(T(\frac n3), T(\frac {2n}3)) + C(n)$$. If $$C$$ is non-decreasing (which is usually the case), we have $$T(n) = T(\frac {2n}3) + C(n)$$, so using the master theorem if $$C(n) = \Theta(\log^k (n))$$ (for $$k \geq 0$$) the solution is $$T(n) = \Theta(\log^{k+1} (n))$$. If $$C(n) = \Omega(n^c)$$ for some $$c > 0$$ and it satisfies the regularity condition then $$T(n) = \Theta(C(n))$$.