Question

In lecture 3, around minute 44 (the 4th program in the code sheet), the prof is describing how the approximate number of guesses can be found by dividing (x) by (epsilon squared). Can anyone explain the math or the mathematical concept behind this? Thank-you!

Answer 1

I would look into theoretical analysis.

http://en.wikipedia.org/wiki/Algorithmic_efficiency

There is also a lot of discrete mathematics in computer science. There is a free book on it here:
http://aimath.org/textbooks/approved-textbooks/

The description makes it look reasonable for any computer science student. It does not require calculus.

Answer 2

Thank-you! I will add this to my evening reading.

Answer 3

I signed up exactly to ask that question! At 42:20 he says "12345 / 0.01 squared equals to 26.897", which does not. It equals to 123450000. It is probably a simple mistake, but I feel like it's an important part and I don't understand how he got 26.897. Could someone explain that to me?

Answer 4

I found the answer, if anybody has the same problem, in this case it's
>>> math.log(12345/0.01**2, 2)
26.879...

Answer 5

That's right! Could you let me know how you figured it out, if you have time? I'm brushing up on calculus alongside learning Python and this kind of thing doesn't come intuitively to me. Thanks for posting your answer!

Answer 6

Sure! I played around a bit trying to get that number and I checked the Wikipedia article on bisection search and logarithms and found the formula: (y = b^x) <=> (x = logb(y))

In this case, we want to find x, which is the number of guesses needed to find the answer.

0.01 is defined by epsilon.

y is equal to the total number of guesses from 1, 1.01, 1.02, ..., 1234.09, 12345 (12345/0,01^2 = 123450000)

Since we reduce the possibilities in half each iteration, the possibilities are reduced exponentially by 2 each time (log base 2)

Basically, you're asking: "how many times do I have to multiply 2 by 2 to get the total number of guesses possible."

So, 123450000 = 2^x
or x = log2(123450000)

I'm sorry if this isn't clear enough, my main language is French, I tried by best. Hope it helps!

Answer 7

Wow, this is amazing! Thank-you so much, I am incredibly grateful for your explanation. Merci mille fois :)