0
$\begingroup$

I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book :

Initially, the number of candidates is n; after the first call in a binary search, it is at
most n/2; after the second call, it is at most n/4; and so on.

What if n is a odd number ?

$\endgroup$
1
  • $\begingroup$ Cannot read the text you copied $\endgroup$ Jul 9, 2023 at 15:57

1 Answer 1

0
$\begingroup$

Strictly speaking, $n$ reduces to at most $\left\lceil\frac n2\right\rceil$, which is $\frac n2$ or $\frac{n+1}2$, depending on the parity of $n$. So you are right. But this can only change the total number of subdivisions by one unit, so it remains essentially $O(\log(n))$.

E.g. $$27\to13\to6\to3\to1$$ vs. $$27\to14\to7\to4\to2\to1.$$


A common technique to handle cases with uneven partitions is to assume that $n$ is a power of $2$, so that all divisions are exact. Then for other $n$, you just notice that the number of partitions is intermediate between those for the bracketing powers of $2$. (E.g. $16<27<32$.)

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