Time complexity of an uneven binary search

Question

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?

• Command Master: 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.
• Jack Sack: $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
• Command Master: The solution depends on $C(n)$. If $C(n) = O(1)$ then it's $T(n) = O(\log n)$.
• Jack Sack: I'm reasonably confident in saying that for $\mathcal{O}(n)$ but I was unsure about the $\Theta(n)$ complexity

Answer 1

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))$.