Question

Lecture 3 can anyone explain why epsilon determines the number of iterations in the bisection search he used some strange formula. Thanks

Answer 1

Epsilon is an error margin that measures how exact you want your answer to be. The closer you want to get to the actual value, the smaller you make epsilon, and more iterations are required.

Answer 2

Yes, i understood that but he used a calculation to determine almost the number of iterations which i did not understand\[12345 \div \epsilon squared\]

Answer 3

in OCW or edX ?

Answer 4

ocw at min 41:40

Answer 5

He doesn't really explain that calculation, but it seems to make pretty good sense intuitively based on what I said earlier.

Answer 6

ook thanks i tried it out and well if you go based off just his words its WRONG... so i though i was going a little crazy but intuitively yes i understand i was hoping it would help me later on.

Answer 7

i can't find the lecture, but maybe this will make sense. For convenience, i am looking for a number between 0 and 1.
0............1/2............1 my first guess is 1/2 - too high
0...........1/4.............1/2 narrowed it down to between 0 and 1/2
0...............1/8...........1/4 1/2 again - but i can't be off by more than 1/4
each iteration narrows my search by 1/2, and after n tries, i can't be off by
more than (1/2)*(1/2)........*(1/2) = (1/2)**n
i'll consider myself done if my guess is < epsilon. if epsilon is 1/2, i am done quickly -
but if epsilon is small, 1/1024, say, it may take me 10 guesses before i am certain
to be that close. the idea is that with each try, we restrict the possible error more, but
if epsilon is small, it may take a lot of guesses. This could be made more mathematically
precise, but maybe it gets the idea?

Answer 8

number iterations should be determined by the size of the search space and the tolerance.