Consider the following procedure:

x is an integer

MAGIC (x)

1 if x > 0

2 then MAGIC (x/2)

3 if x is odd

4 then print 1

5 else print 0

a. Given a positive integer x, what does this procedure print on the screen? Do not prove your

claim. (Your statement should be simple and shouldnt simply rephrase the computation of

the algorithm in mathematical terms.)

b. Let the input size be the value of x. Give a recurrence for the running time of the algorithm

in terms of the value of x.

c. Solve this recurrence using whatever method you like, in order to determine the running time

of procedure MAGIC.