How fast does the bisection search converge?

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} \]