Question

Why is the search space size towards the end of lecture 3 the endpoint over epsilon squared? I do not understand the squared part. Thanks.

Answer 1

The goal is to find the sqrt of 12345
The search space is 12345/epsilon^2 because the variable ans^2 is within epsilon of x.
i.e. ans divies up the search space at least
\[\log_{2} (12345/epsilon^2)\]
times

Answer 2

Hugely helpful, thank you!