Question

so, i'm doing the OCW and i'm on lecture 3: problem solving...

on bisection searches
can someone please help me with this. i'm completely baffled.
i understand the search and what it's doing. what i dont understand is how he managed to get 26 as the answer for number of searches on the 12345.0 problem.

he describes the solution as 12345.0 divided 0.01 squared. but that comes out to be 123450000, so there must be a different formula to determine the 26 tries.

can someone please give me an idiots guide on how he comes up with 26? because everything else in that lecture was completely understandable, just not HOW he got 26

Answer 1

Yes, I have discussed this before with people... he made a mistake in what he said.

Answer 2

Because it is a bisection, or halving each time, it has to do with some log base 2 stuff. They go into this sort of evaluation more in discrete mathematics and algorithm classes.

Answer 3

is this something that i need to know before continuing? or is he simply trying to show how the program found the answer? if it's just an example then i'll be happy to file it as not needed and continue on.

Answer 4

i figured it out!!!!!

he said the formula to do it was 12345/0.01^2

which comes to 123450000

if you then take log base 2 of 123450000, you get 26 and some change.

i think someone else had stated that elsewhere, maybe on youtube? but it was not really clear somehow.

so the actual forumla is log2(x)/0.01^2.

it took a while for me to figure out that i needed to do the x/0.01^2 before finding log2 (i'm a bit of a simpleton).

Answer 5

someone actually listed the formula on youtube, but the way they listed it, didnt come out with the right answer...

Answer 6

the correct method should be

log2(12345/0.01^2)

or

log2(x/0.01^2)

but sadly it does not work with x=25.. or any other random number that i tried. so i dunno what the true formula is, but that is how i got the answer 26.

Answer 7

that equation, ONLY works, with 12345.

it works with NO other number at all, so there is still something missing from the formula, and i feel that it was a fluke that he arrived at 26

Answer 8

\(log_2(123456/.01^2)\approx 30\)
\(log_2(9130982309876/.01^2)\approx 56\)

It looks like it works.

Answer 9

If you make it more precise, as in make epsilon smaller, the number of steps goes up:
\(log_2(9130982309876/.0005^2)\approx 65\)

And down if you go the other direction:
\(log_2(9130982309876/.5^2)\approx 45\)

So it follows logical predictability for the type of evaluation you want to do. Larger numbers or more precision results in more bisections needed. Smaller numbers or less precision makes for less bisections needed.

Answer 10

so the higher the number is, the more likely his formula will work but in order for it to be accurate for lower numbers like 25 we need to change epsilon to like .1 ?

Answer 11

No. \(log_2(25/.01^2) \approx 18\) It is more likely that small numbers will not work well in this sort of formula or that it will still take a lot of steps.

Answer 12

so how does he suspect that we can predict the number of guesses accurately for all numbers, if this formula is only accurate with larger numbers?

Answer 13

or is it that with smaller numbers we shouldnt need to program something to calculate it?

Answer 14

The number of guesses is the worst case, i.e. in the most unfavourable case. The actual number can be anything from 1 to the "predicted" number.
Look at it this way:
if you are searching an item out of 2, you need only one try. (note: \(log_2{2}=1\)
if you are searching out of 64, you need 6 tries (check it) which equals \(log_2{64}=6\).
I don't know about the 12345.0 problem, but if the precision requires to be 0.001, then there is an equivalent of 123450000 items to choose from and \(log_2{123450000}=26.9\).
If you can post the 12345.0 problem in detail, we can look at it more closely.

Answer 15

mathmate, it is a simple bisection search for a square root approximation.

meshane2, the key is in what mathmate said about worst cases. You are not seeing how long the search will take. You are estimating how bad the search can be. In more advanced programming, these estimates can save a lot of time. Why? Because if a particular method (algorithm) is better for some specific case, then using that method for millions of calculations ends up saving tons of computer time.

The example in the class is simple. Any single event in a computer is simple. However, programs are generally not simple. All these simple examples and events are put together into far more complex structures that eventually build up to an entire program that you might install on a computer or phone. But starting with those in a class is not practical. So they show you the simplified case as an example of how using some math can help you predict the worst case, which also informs about the average for repeating things several times.

Answer 16

so his formula for getting that guess doesnt need to be accurate, it just needs to give us a ballpark so that we can understand what steps to take next? if so then i can understand and deal with that, and will happily move on to the next lesson.

Answer 17

Yes, you are correct. That is all that this type of evaluation is about. It is meant to give you a ballpark to look at for evaluationg a worst case and therefore have an idea what method would be best.

Answer 18

ty for the help :)

Answer 19

\[number of divisions = \frac{ x }{ \sqrt{x + \epsilon} - \sqrt{x - \epsilon } }\]
\[\log_{2} (number of divisions) = Largest number of tries w/ bifurcation\]
I did the math and I think this is the equation for the possible number of divisions. When I took the log base 2 for x = 12345 and epsilon = .01 , I got roughly 27, so that was pretty accurate. When I did it for 25 and .01 I got 13.6 and the number of needed guesses was 13. I believe it is accurate; however, because it only gives the highest number of possible guesses, it will not always be this close, but the number of guesses should never exceed the answer given by the equation, and if it does then the equation is wrong. Additionally, as epsilon gets closer to 0 (smaller and more precise), the number of divisions goes to infinity, which makes sense.

It really bothered me when he said that stuff in the video, I was super confused, thus I put a lot of time into this. I can usually figure out most stuff but I could not see where he was getting that answer or equation. So I kind of overdid it. I'm glad to hear that other people were confused about it too. If anybody would like to see the work for this I can upload it. Thanks!

Answer 20

yah, he just made a mistake and they did not footnote correct it. There are later classes where they go into this topic in a lot more detail.

Answer 21

this lecture and the one after it, resulted in me stopping the vdieos. the prof is simply too difficult to follow and does not take any time at all to let us understand whats going on. and the TA explanations can sometimes be a little vague as well. i've started other courses on udemy and codecademy which have helped my understanding of these two lectures. i will probably come back and finish these lectures after i've had more experience with coding. this is definitely not a 'beginners' course. thanks for the answers and help though guys :)