-4
$\begingroup$

Suppose $k$ and $n$ are natural numbers such that $2^{2^k} \lt n \lt 2^{2^{k+1}}$. I am curious how many integers are there in the interval $\left[2^{2^k}, 2^{2^{k+1}}\right]$ in terms of $n$.

I need to know this because some student claims doing a binary search for number $n$ inside the interval above takes $O(log n)$ while I am grading. I feel it shouldn't be the case but I am not able to show any proof.

Thanks.

Improve this question
$\endgroup$
3
  • $\begingroup$ The number of bits in (some standard representations of ) n in the given interval Is between m=2^k and 2m+1. It should take at most 2m queries of a good binary search to determine all bits of n. This is the wrong forum for your question. Also, you need to know what $n$ is in order to answer the question as asked. Gerhard "A Grader Must Know This" Paseman, 2017.04.12. $\endgroup$
    – Gerhard Paseman
    Commented Apr 12, 2017 at 21:14
  • $\begingroup$ The question is reasonably well posed, but definitely not research level. In the future, consider MathSE. $\endgroup$
    – David Cohen
    Commented Apr 12, 2017 at 21:29
  • $\begingroup$ @DavidCohen Thank you for your reply. I realize it should not be here. Thanks for the pointer to MathSE. I am just describing the situation the student has led to. $\endgroup$
    – huoenter
    Commented Apr 12, 2017 at 21:35

1 Answer 1

Reset to default
0
$\begingroup$

In the worst case, $n=2^{2^k}$, which would mean that there are $n^2-n$ integers to check, as $2^{2^{k+1}}=2^{2^k+2^k}=(2^{2^k})^2$.

So the student is validated.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .