Analysis of bisection search

Question

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-1/lecture-3-problem-solving/

In the following video i'm interested from 42:04-43:30 (when he's talking about how many divisions there are) why he's divided the search space by $\epsilon^{2}$ (i.e $0.01^{2}$) in his complexity analysis of the bisection search method for finding a square root? Can anyone elaborate abit on this since he just skips it?

Answer 1

The stopping condition used in the video is a bit unusual for bisection, but would be very common for other techniques. He is stopping once $|g^2-x|<\epsilon$ where $g$ is the current guess. He is not stopping once $|g-\sqrt{x}|<\epsilon$, even though in bisection one can proceed this way. Here $|g^2-x|$ is called the forward error and $|g-\sqrt{x}|$ is called the backward error (I'll use these terms in what follows).

To determine the number of bisection steps required to have the forward error be less than $\epsilon$, one should determine or at least estimate the length of the interval around $\sqrt{x}$ where $|g^2-x|<\epsilon$. If $\epsilon$ is small enough, the half-length of this interval is approximately $\frac{\epsilon}{2\sqrt{x}}$. (I can think of two ways using calculus and one way using algebra to see this. Ask me if you don't understand.) In the example you have $x=12345$, and so you know that $\sqrt{x}$ is less than, say, $200$. So the half-length of the interval is at least $\frac{\epsilon}{400}$. So it is enough to use bisection to make the backward error be less than $\frac{\epsilon}{400}$. Beginning with an interval of length $x$ and taking the midpoint of the last interval generated to be the estimate, this takes at most $\log_2(x/(\epsilon/400))-1$ steps. This is less than 29. If I replace the $200$ with a better estimate like $112$, I can shave it down to 28 steps.

I do not really see how making the backward error less than $\epsilon^2$ ensures that the forward error is less than $\epsilon$; indeed, $(\sqrt{12345}+10^{-4})^2-12345>2 \cdot 10^{-2}$. Presumably this is either an error in the video or a misunderstanding on your part.