3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Oct 27, 2023 at 3:25
  • $\begingroup$ $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 $\endgroup$
    – Jack Sack
    Oct 27, 2023 at 3:29
  • $\begingroup$ The solution depends on $C(n)$. If $C(n) = O(1)$ then it's $T(n) = O(\log n)$. $\endgroup$ Oct 27, 2023 at 3:29
  • $\begingroup$ I'm reasonably confident in saying that for $\mathcal{O}(n)$ but I was unsure about the $\Theta(n)$ complexity $\endgroup$
    – Jack Sack
    Oct 27, 2023 at 3:31

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.