minimum number of iteration in Bisection method

One root of the equation $e^{x}-3x^{2}=0$ lies in the interval $(3,4)$, the least number of iterations of the bisection method, so that $|\text{Error}|<10^{-3}$ is

(a) $10$

(b) $6$

(c) $8$

(d) $4$

• $10^{3}$?? Isn't it $10^{\color{red}{-}3}$ – Surb Dec 8 '14 at 16:38
• @Surb what do you mean? – Empty Dec 8 '14 at 16:39
• I assume you mean $10^{-3}$. In this case it will be $-\log_2(10^{-3})$ (possibly plus or minus one depending on how you define the start and end of the algorithm). – Ian Dec 8 '14 at 16:39
• Yes...It was a mistake.... – Empty Dec 8 '14 at 16:42
• For any numerical method, it is very hard to find a non-trivial lower bound on the convergence rate (or iteration counts) a priori which strongly depends on how lucky your initial guess is. – Algebraic Pavel Dec 8 '14 at 17:22

It's very easy. For Bisection method we always have $$n\ge \frac{\log{(b-a)}-\log{\epsilon}}{\log2}$$ Here we have $\epsilon=10^{-3}$, $a=3$, $b=4$ and $n$ is the number of iterations $$n\ge \frac{\log{(1)}-\log{10^{-3}}}{\log2}\approx 9.9658$$ Then $n=10$.
• The number of iterations can be less than this, if the root happens to land near enough to a point $x = 3 + \frac{m}{2^{n}}, \; m = 0,1,\dots, 2^{n},$ where $n$ is the iteration number. For example, if the root was at $x = 3.5001,$ 10 iterations wouldn't be necessary to achieve the error bound. 10 is an upper bound, the question seeks the least number of iterations. – Merkh Oct 30 '16 at 23:17