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.



How many integers between $\left[2^{2^k}, 2^{2^{k+1}}\right]$?
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.


