In bisection search example (lecture 3), Guttag asks the class 'how large was the search space?' The answer was 'roughly x / epsilon **2'. How does one arrive at this answer?

Question

In bisection search example (lecture 3), Guttag asks the class 'how large was the search space?'  The answer was 'roughly x / epsilon **2'.  How does one arrive at this answer?

e.mccormick · Answer

Well, how many items get searched and why is it that number?  That defines the search space.

anonymous · Answer

I get why the search space would be at least x / epsilon, and that it ought to be resolved even more finely than that.  Is x / epsilon**2 the 'real' answer?  Or would it be as correct to have chosen something like x / (2*epsilon)?

The code is: 

x = 12345
epsilon = .01
numGuesses = 0
low = 0.0
high = x
ans = (high + low)/2.0
while (ans**2 - x) >= epsilon and ans <= x:
	#print low, high, ans
	numGuesses += 1
	if ans**2 < x:
		low = ans
	else:
		high = ans
	ans = (high + low)/2.0
print ‘numGuesses = ‘, numGuesses
print ans, ‘is close to square root of’, x

anonymous · Answer

Sorry, just ignore the print statements and question marks, they aren't important.  I must have pasted something with the wrong encoding.

e.mccormick · Answer

Each time you search half as much, so your search soace is expotentially shrinking.