# What is the rate of convergence for the bisection search algorithm?

Consider the initial search region to be $$L$$. On each step, we halve the search region size. That is, after the $$n^\text{th}$$ step, the remaining search region is $l_n = {L \over {2^n}}$.

Let's set the convergence criterion ($$\epsilon$$) w.r.t. the size of the remaining search region as $l_n = {L \over {2^n}} \leq \epsilon$

Now, we can solve for $$n$$ to see how many steps we will need to achieve this limit

${L \over {2^n}} \leq \epsilon \Leftrightarrow 2^n \geq {L \over \epsilon} \Leftrightarrow n \geq \text{log}_2 \Big({L \over \epsilon}\Big)$

Thus, we will need $n = \lceil\text{log}_2 \Big({L \over \epsilon}\Big)\rceil$ bisection steps to achieve $$\epsilon$$-level of convergence.

Bisection search is said to converge linearly, as the error ratio towards 0 between two steps is within $$[0, 1)$$

${ {l_{n+1} - 0} \over {l_{n} - 0}} = { { L / {2^{n+1}} } \over { L / {2^n} } } = { { 2^{n} } \over { 2^{n+1} } } = {1 \over 2}$