0
$\begingroup$

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)$?

$\endgroup$
4
  • $\begingroup$ can you link the paper? $\endgroup$
    – JimN
    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$
    – JimN
    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$
    – EvaMGG
    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$
    – JimN
    May 6, 2023 at 10:00

1 Answer 1

2
$\begingroup$

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).$$

$\endgroup$
1
  • $\begingroup$ Sorry, $n+1$ was a mistake. $\endgroup$
    – user16034
    May 11, 2023 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.