2
$\begingroup$

We know Binary search on a set of n element array performs O(log(n)).

We have this recursive equation through which the search space is reduced by half in each iteration, after a single comparison.

T(n) = T(n/2) + 1 

Either by applying Master's Theorem or analytically we arrive at the complexity of it as log(n)

If I introduce bias, in the search by unequally partitioning the array instead of equal halves, How would the worst case time complexity change?

The unequal partitions are t * n and (1-t) * n where 0<=t<=1

This is a mathematics question as it involves asymptotic analysis and hence I don't wish my question to be downvoted.

$\endgroup$
  • $\begingroup$ If I understand what you're asking correctly, wouldn't the worst case complexity be $O(n)$ due to it potentially using a partition size of $1$ and $n - 1$, requiring on average $\frac{n}{2}$ checks? Note it should never be worse than $O(n)$ as any type of biased binary search should only ever check each value at the most $1$ time. $\endgroup$ – John Omielan May 18 at 2:15
  • $\begingroup$ Correct. But I want to come across with an analytical way to calculate the worst case complexity for any particular value of t. In general, it is evident that the worst case complexities are O(n) when t=0 and O(log(n)) when t=1/2. $\endgroup$ – Argha Chakraborty May 18 at 6:04
  • 3
    $\begingroup$ There's nothing special about $t = \frac{1}{2}$. As long as you reduce the problem size by a factor of $t$, for any $0 \leq t < 1$, you will get logarithmic running time. $\endgroup$ – Joppy May 18 at 7:16
  • $\begingroup$ That is what I want to prove . $\endgroup$ – Argha Chakraborty May 18 at 7:33
2
$\begingroup$

In the worst case scenarios, where $t = 0$ or $t = 1$, and assuming that at least one value will always be checked, then as I stated in my comment, the average number of checks would be $\frac{n}{2}$ and the maximum number would be $n$. However, for $0 \lt t \lt n$, where $tn \gg 1$, then as indicated in the comment by Joppy, the number of steps in the worst case scenario would be logarithmic.

To see this, let

$$u = \max(t, 1-t) \tag{1}\label{eq1}$$

The worst case would be that the value is always in the larger partition after each step, with $n_i$ being the size of this partition after $i$ steps, and with $n_0 = n$. Thus,

$$n_i = un_{i-1} \; \forall \; i \ge 1 \tag{2}\label{eq2}$$

As such, $n_1 = un$, $n_2 = un_1 = u^2 n$, etc., to get that

$$n_i = u^i n \; \forall \; i \ge 0 \tag{3}\label{eq3}$$

The search will eventually end after $m$ steps where

$$u^m n \approx 1 \tag{4}\label{eq4}$$

Note this is similar to the concept of the amount of time for exponential decay to cause a substance to eventually disappear, with the worst case number of unbiased binary searches being about the number of half-life periods. To use a value $\gt 1$ for logarithms, let

$$v = \frac{1}{u} \tag{5}\label{eq5}$$

so \eqref{eq4} becomes

$$n \approx v^m \; \implies \; m \approx \log_v(n) = \log_v(e)\ln(n) \tag{6}\label{eq6}$$

For $t = u = \frac{1}{2}$, then $v = 2$ and \eqref{eq6} gives $m \approx (1.44269)\ln(n)$. With a relatively extreme case of $t = \frac{1}{1001}$, then $u = \frac{1000}{1001}$ and $v = 1.001$, so \eqref{eq6} gives $m \approx (1000.49991)\ln(n)$, i.e., about $693.5$ times as large. Nonetheless, it's still generally considerably faster than just checking each value since, for $n = 10^{12}$, \eqref{eq6} gives $m \approx (1000.49991)(27.63102) \approx 27644.8$, so it's about $\frac{10^{12}}{27644.8} \approx 3.61731 \times 10^7$ times faster.

$\endgroup$
1
$\begingroup$

The cases $t=0$ and $t=1$ do not correspond to a terminating algorithm. Otherwise, the behavior remains logarithmic.

In the worst case, the array is every time reduced according to the smaller of $t$ and $1-t$; WLOG, let $t$.

After $k$ steps, we approximately reduce from $n$ to $nt^k\sim 1$, so that $k\sim-\log_tn$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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