Reading a paper, I have found an algorithm that uses binary search to find a number between $0$ and $n\in\mathbb{N}$. The stopping criterion for this binary search is that $t_2-t_1<\frac{1}{k^2}$ where $k>=1$ is a natural number and $t_2>t_1$. Then, it is said that the number of iterations of the binary search is at most $k\cdot{\text{log}_{2}}(n)$. Why the number of iterations is $k\cdot{\text{log}_{2}}(n)$?
4
-
$\begingroup$ can you link the paper? $\endgroup$– JimNCommented May 6, 2023 at 9:21
-
$\begingroup$ Is this search finding a real number (a non-integer number) in the range of [0,n] ? $\endgroup$– JimNCommented May 6, 2023 at 9:23
-
$\begingroup$ I assume that it is a search for a non-integer number due to the stopping criterion. $\endgroup$– EvaMGGCommented May 6, 2023 at 9:31
-
1$\begingroup$ The statement that it takes $k log(n)$ steps is in the proof of Theorem 7. Compare Theorem 7 to Theorem 1. At the end of the proof of theorem 1, it mentions that a procedure is repeated $k$ times (I believe this is to de-randomize the approximation algorithms and thus making a deterministic algorithm). At the end of the proof of theorem 7, it could be that this $k$ factor in counting the steps of binary search is due to the number of times Algorithm1 is run for the purpose of de-randomization. $\endgroup$– JimNCommented May 6, 2023 at 10:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
After $m$ iterations, the interval size is
$$\frac{t_2-t_1}{2^m}=\frac{n}{2^m}.$$
This becomes smaller than $k^{-2}$ when
$$\frac{n+1}{2^m}\le\frac1{k^2}$$
or
$$m\ge\log_2(k^2n)=2\log_2(k)+\log_2(n).$$
-
$\begingroup$ Sorry, $n+1$ was a mistake. $\endgroup$– user16034Commented May 11, 2023 at 10:27