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