# Binary search calculating complexity big o

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 ?

• Cannot read the text you copied Jul 9, 2023 at 15:57

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