I was confused in lecture 3 towards the end of the bi-section search topic the professor said that to estimate the number of guesses you divided x12345 by epsilon^2, and he went on to say that the approximate was 26.89 which is pretty close to the actual number of guesses taken by the program. I am having trouble repeating this since
12345/(0.01)^2 is no were near 26. Could someone clarify how to eatimate the guesses of bisection search and how the professor got 26.89?
Thank you

Question

I was confused in lecture 3 towards the end of the bi-section search topic the professor said that to estimate the number of guesses you divided x12345 by epsilon^2, and he went on to say that the approximate was 26.89 which is pretty close to the actual number of guesses taken by the program. I am having trouble repeating this  since   
12345/(0.01)^2 is no were near 26. Could someone clarify how to eatimate the guesses of bisection search and how the professor got 26.89? 
Thank you

e.mccormick · Answer

In the Delta-Epsilon definition, is on the y axis.  In the problem, the .01 is on the x axis.  That is one possibility.

I would have to re-watch things to get a better idea of where the information is... but I think this has been gone over before.

e.mccormick · Answer

Hmmm...  google is not being nice and helping me find it here.

e.mccormick · Answer

Hmmm.... looking at rhe transcript... http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-1/lecture-3-problem-solving/lecture-3-problem-solving/ggxY20cXql8.pdf Yes, it is misstated.

e.mccormick · Answer

In Big O notation it is $O(\log n)$, but you need to know Big O notation for that to make sense. That is not a topic I really understand enough to describe. http://en.wikipedia.org/wiki/Big_O_notation

anonymous · Answer

thank you for clarifying

e.mccormick · Answer

12345/x=26.897
12345/26.897=x
x=458.97311967877458452615533330855

So what is the root of that:
458.97311967877458452615533330855^.5
21.423657943469284781581968172817

So, something that gives about 21.424 as a result and is related to the problem mathemetically.

anonymous · Answer

if I take 12345 and divide by 2 and keep dividing by 2, the 26th time I get 0.00018 which is close to 0.01^2. There is a relation , I am getting close.

e.mccormick · Answer

You are saying:
$\dfrac{12345}{2^{26}}\approx .01^2$

So what you want is the way to do:
$\dfrac{12345}{2^{x}}\approx .01^2$
Which can be generalized:
$\dfrac{12345}{2^{x}}\approx \epsilon^2$

$\dfrac{a}{2^{x}}\approx \epsilon^2$

$\dfrac{a}{\epsilon^2}\approx 2^{x}$

$\log_2\dfrac{a}{\epsilon^2}\approx \log_22^{x}$

$\log_2\dfrac{a}{\epsilon^2}\approx x$

$\log_2\dfrac{12345}{.01^2}\approx x$

OK, so lets see.

$\log_2123450000\approx x$

$26.879351596\approx x$

So yes, that works.  And that makes a lot of sense with the Big O notation concept of this being O(log n) of a binary (base 2) search.

anonymous · Answer

precisely, I was halfway there but was a little rusty on my math. Thank you

e.mccormick · Answer

Well, I need to go back through a bunch of math at times when I answer questions here, so it helps.... but there is an online calculus class I really should take since I am forgetting most of that with disuse!

anonymous · Answer

Same here, I love math but inevitably forget some due to disuse.

anonymous · Answer

so how do we figure it out WITHOUT big o notation?

e.mccormick · Answer

Big O is just an application of math specific to these things.  If you want to learn efficiency and algorithms, you need the math or you need to memorize how efficient each type of algorithm is.