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?

Improve this question
$\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$ Commented 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$ Commented 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$ Commented 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$ Commented Oct 27, 2023 at 3:31

1 Answer 1

Reset to default
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))$.

Improve this answer
$\endgroup$

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.