Question

Determine the complexity, in terms of the number of guesses, needed to determine a number between1and$2^{\mathrm{n}}-1$ by successively guessing the bits in its binary expansion.

Short answer

O(n)

Step-by-step solution

Step 1

Algorithm for guessing the number

We need to devise an algorithm for guessing a number between 1 and $2^{\mathrm{n}}-1$.

Let somebody choose a number between 1 and $2^{\mathrm{n}}-1$.

Then ask the person to write the number in binary notation.

You first ask the person if the first bit is a 1.

Then you ask the person if the second bit is 1 .

Then you ask the person if the third bit is 1.

And so on, until you asked this for the nth bit.

When you know the answer to these questions, then you know the number in binary notation and thus you can then rewrite the number in decimal notation.

Step 2

Complexity of algorithm

In the algorithm, we made a n guesses (one guess per question asked) and thus the complexity of the algorithm is then O (n) in terms of the number of guesses.