Question

My question deals with material discussed in Lecture 3 around 42:11. I'm having a hard time understanding why each element in the range between low and high has at least a difference of 0.01^2 with the element next to it. I get the whole 12345/difference --> plugging it in to this formula T(n) = O(log n) part. So I can see how he gets to 26.8... when he understands the difference between each consecutive element is roughly 0.01^2. The part I don't get is why it's 0.01^2 difference between each element. Please explain as simply as you can :)!

Answer 1

Because the algorithm he's using is estimating that the root is the number divided by epsilon, which is \(0.01^2\). So each of the elements end up being a multiple of epsilon.

Answer 2

It helps if you say which year. I am guessing you mean the 2011.

This topic starts around 27 minutes in, where he talks about things taking longer and computational complexity. Eventually he goes over what is involved in determining the speed:

Distance of square root from starting point.
Value of Epsilon (how accurate you want it)
The increment, because how many loops you take depends on how small the the steps are.

Now, Epsilon is 0.01 in the guessed root. However, the guessed root is squared to make a new guess. 0.01^2 becomes the difference in the tested result.

Answer 3

Or more accuratly, it is squared to test the present guess, and based on how close you are, you either have an answer or make a new guess.

Answer 4

Espex: abs(ans**2 - x) >= epsilon... the root is not the number divided by epsilon. For instance, imagine the number is 25. The epsilon is 0.01. This means that as long as your root squared is an absolute value of 0.01 or less away from the number, it is okay to be used as a root. So that being said, I don't really understand how your response has anything to do with why each element in the spread of low to high is 0.01^2 apart in the bisection search.
E.mccormick: My question specifically deals with the bisections search example, in Lecture 3 of year 2011. His reasoning for it is at 42:10.

Answer 5

@Hamia12 , my response was that the guesses, based on his lecture, were going to be in a number of steps that equaled close to the value divided by epsilon, this was how he made the initial guess at what the root of the number was.
Given your convoluted question it was difficult to discern exactly what your difficulty was however, so if I was unable to answer your question specifically, perhaps you could clarify your query.
Since you asked why the elements were approximately epsilon apart from each other, I was explaining that the steps were expected to be that much apart.

Answer 6

I see. I'll clarify the question:

Professor Guttag states a few intelligent individuals came up with an algorithm that will estimate the square root of a number using a bisection search. For instance, if your desired number is 25 (assigned variable x), this bisection search will require you to identify a low, and then based on the low value and the high value, it will pick a number exactly in between and then square it. If the resulting answer is above that of the number (ans^2 > x), then it will know to look on the left hand side of that middle number (ans). It will also set that middle number now as the new "high". It will keep doing this, until it finds an ans that when it squared, it is epsilon distance away from the original number (x). This particular equation is written as abs(ans^2-x)=< epsilon; of course, in the lecture video, he writes a while loop of "while abs(ans^2-x)=> epsilon..." so that when it does not follow that loop condition, it breaks out of the loop, and prints the algorithms approximation of a root for x.

He then says that you can estimate the number of guesses the computer makes by knowing how many elements there are. Once you know how many elements there are, you can plug it in T = number of guesses = log (base 2) (number of elements) = which should equal 26.8... in his example. He also says to find out the approximate number of elements you must divide the spread of data (initial high - initial low = 12345 - 0) and then divide it by the value of difference between each element in that spread of data. He also proceeds to say that this value of difference is epsilon^2.

* My question is: Why is this value of difference epsilon^2. Please explain this in the most rudimentary, basic, simple, easy, clear, elaborate, and logical way possible.

Answer 7

You do not want an elaborate explanation.
Elaborate: adjective. complicated - complex - detailed

Answer 8

I said elaborate because I didn't want a one sentence explanation.

Answer 9

Btw, I think I answered my question. A gap of epsilon between elements is not enough because for instance, what if the number (x) was 25 and your epsilon was 0.01. Then you are allowed to have any root that provides you with an answer between 24.99 and 25.01. This is a gap of 0.02. Now imagine a root candidate, a, but the square of this root minus the number is very slightly greater than epsilon. You have no choice but to go up an increment of 0.01 --> (a+0.01). However, (a+0.01)^2 is a^2+0.02a+0.02a+0.0001. As you can see, if the previous root was 1 or greater, this next root squared is already 0.0201 greater than the last root squared, and you might have possibly leaped over the acceptable squared roots, and thereby missed the corresponding root. However, if you have a gap of epsilon^2 between elements, you would have (a+0.0001)^2, which is a^2+0.0002a+0.00000001, thereby avoiding the possibility of missing an acceptable squared root and its corresponding root. Correct me if I'm wrong.

Answer 10

I would say that you are correct, epsilon is just a tolerance used to ensure that you find a value as close as you can, avoiding the potential you describe.