I am confused about how the professor calculated the size of the search while he was discussing the bisection method in the third lecture (approximately at the 40 minute mark)?

Question

e.mccormick · Answer

You can link the Youtube videos with a time point reference.

As for how he did it, there are some principals in math he is using.  For example, the powerset for any set has a known number of elements.  A powerset is every possible subset of a set.  Say you have the set $A$ and $|A|$ was the magnitude or number of elements in the set.  Then the powerset $\mathcal P$ has a known magnitude findable as:

$|\mathcal{P}(A)|=2^{|A|}$

Through math like this, you know how many possibilities there is in something and how long it would take to check every possible combination of subsets.

I am not saying he used this exact principal, but rather that it is one that you end up learning when you take advanced math.  He just knows more of these mathematical principals and is applying them.

anonymous · Answer

https://www.youtube.com/watch?v=ggxY20cXql8#t=2341 Powersets may be an advanced mathematical technique, however, he describes dividing the number 12345/epsilon^2. I am not clear about why he divided by (0.01)^2 rather than 0.01.

anonymous · Answer

It confuses me to. I think 12345/epsilon^2 is the number of elements in the search set. He said that during a bisection search there's a maximum of $$\log_{2} n $$ where n is the number of elements in the search set. If you take n to be 12345/epsilon^2 , doing the math , I got 20.xx something. It confuses me I don't if whether he said something wrong or it's me who doesn't know how to do the math!!

e.mccormick · Answer

Epsilon, $\epsilon$, is how far guess g when squared needs to be within the value desired to be considered the square root.  So if number n is what you want the root of, then if $|g^2-n| \le \epsilon$ you are saying it is a good enough root.

As for how many guesses this will take, it depends on how precise $\epsilon$ is.  The smaller $\epsilon$ is, the more guesses it will take to be within that distance.  So to calculate the number of guesses you need something that accounts for the number, $\epsilon$, and the fact that $g^2$ is involved.

e.mccormick · Answer

Ah, you said size of search, not number of guesses.  They are sort of related.  At that point he is using the fact that he is taking half each time.  So you have somewhere between 0 and 12345 and if you were to divide that up evenly and going through it, the size of the search would be 12345/.01.  But, when you test one and only one thing, then cut it in half based on how close it is to .01, you are dividing off tons of the possibilities each time.  See, the first test you cut the possible choices in the search space in half.  The second time you cut that in half again.  If I am thinking about this right, each of these divisions you have two possibilities in the search space: within $\epsilon$ but high and within $\epsilon$ but low.

e.mccormick · Answer

It really depends on which thing you are talking about.  How many possible elements are being searched or how many guesses are needed to perform the search.

anonymous · Answer

This is an excellent question and I agree that the professor was being rather too loose in the lecture. In fact, when you set x = 123456789, the bisection method makes 45 guesses, while $\log_2\frac{ x }{ 0.01^2 } \approx 40.1$ so dividing by epsilon squared doesn't yield the exact size either.

Suppose we are looking for the square root of $x$. After $n$ guesses, the bisection method reduces the size of the search space into $\frac{x}{2^n}$. This means that the maximum distance between the $n$th guess and the actual square root of $x$ is equal to $\frac{x}{2^n}$. But the criterion for terminating the search isn't that the distance between the guess and square root of $x$ is less than epsilon. Rather, we require that the distance between the square of the guess and $x$ to be less than epsilon. In other words, if we denote the $n$th guess as $g_n$, then we end our search when $|g_n^2 - x| < \epsilon$, not when $|g_n - \sqrt{x}| = \frac{x}{2^n} < \epsilon$.

So this shows why dividing by epsilon doesn't give a proper number of guesses, but it also shows neither does dividing by squared epsilon.

e.mccormick · Answer

Which is probably why he calls it an estimate and why the real application of this part is gone over in another class.  Usually with algorithms, I think.