Question

A Mystery Algorithm

Input: An integer n ≥ 1

Output: ??

Find P such that 2 P is the largest power of two less than or equal to n.

Create a 1-dimensional table with P +1 columns. The leftmost entry is the Pth column and the rightmost entry is the 0th column.

Repeat until P < 0

If 2 P ≤ n then

put 1 into column P

set n := n − 2 P

Else

put 0 into column P

End if

Subtract 1 from P

Return the filled-in table

(a) In general, what is the output of the Mystery algorithm?

(b) What is the run time of the Mystery Algorithm? Your answer should be a function of n. You may assume that “Find P such that 2 P is the largest power of two less than or equal to n” takes Θ(1) time to compute.

Answer 1

a) CASE STUDY:
Let us Consider n=5.
Then, 4 is the closest power of 2 to 5.
Therefore, P=2 as 2^2=4.

We create a one-Dimensional array of 3 columns, arranged from MSB(P) to LSB(0). P+1, here represents the minimum no. of bits required to represent the Number n.
Here we create an array of size 3, where the first index is 2 and the last index is 0.

Dry Run

n=5,P=2
We Put 1 into the current column no. if 2P<= n and then decrease n by 2^P
n=5, A[2]= 1
n=5-2*2=1, Decrease P by 1 every time
P=2-1=1
Continue until P <0

n=1, P=1
If (2*1<=1) false
A[1]=0
P=P-1=0
Continue until P <0

n=1, P=0
If(2*0<=1) true
A[0]=1
n=1-2*0=1
P=0-1=-1
Continue until P <0

Exit.

The program returns: 101 marked from 2 to in an Array
Therefore, the general work of the program is to return the binary value of the given number n.

b) The algorithm basically runs it's main loop for the number of times of the nearest power of 2 of the given number n, which is basically = floor((log₂n))+1 or generically speaking in terms of n Θ(log n).