I compare

Computer Science Level 2

1
2
3

i=1
while i <=n:
    i*=2

What is the number of comparisons made in the execution of the while loop shown above?

Details and Assumptions

$n\geq 1$

\left\lceil \log_2n \right\rceil

\left\lfloor \log_2n \right\rfloor +2

n

\left\lfloor \log_2n \right\rfloor

\left\lceil \log_2n \right\rceil +2

1 solution

Shourya Pandey
May 15, 2016

Essentially, we keep doubling $i$ unless it doesn't exceed $n$ . The values compared in the while loop are

$1,2,2^2,...,2^k,2^{k+1}$ ,

where $k$ is such that $2^{k} \leq n < 2^{k+1}$ , or $log_{2}n - 1 <k \leq log_{2}n$ , so that $k =\lfloor log_{2}n \rfloor$ . In all , $k+2 = \lfloor log_{2}n \rfloor+2$ comparisons were made.

I compare

1 solution

0 pending reports