Question

1. Here is a pseudo-code of a program that takes two non-negative numbers X and Y as its inputs and outputs a number Z. Write this program in C. What does this program do? Explain how it computes the output Z from its inputs X and Y. Determine the big-Oh of this program in terms of its input sizes.                                                                

f (int x, int y)

{

     z = 0; k = y; w = x;

     while (k != 0)

{

          if (k % 2 == 1)

             z = z + w;

             k = k/ 2;

           w = 2 * w;

     }

}

Answer 1

let x=4,y=7

k=7; z=0; w=4;

while(k!=0)

k=7 so,k%2==1 =>z=0+4=4;

k becomes 3

w becomes w = 4*2=8

so,again 3%2==1 => so, z=4+8=12;

k becomes 1

w becomes w=8*2=16

again 1%2==1 so, z=12+16=28;

k becomes 0 and stops and the final z is 28

Timecomplexity for this program is

The lines z=0,k=y,w=x takes O(1) for each assignment so it becomes O(1)+O(1)+O(1)

The while(k!=0) takes O(log n) becauese the k value is changing in terms of k/2 so,the time complexity for this series will be log n.

The if statement takes comparision of one value so,it is O(1)

The addition also takes constant time.

division and multiplication statements takes O(1) for each

so for the entire loop the time complexity will be

O(log n) *(O(1)+O(1)+O(1)+O(1))= O(4 log n)

the entire time complexity wil be O(4 log n)+4

The constant 4 will become less and less significant to the final result so,we ignore that.It again takes O(4*log n)

In this the coefficient 4 becomes insignificant as log n gets large.

So,we the time complexity for this is O(log n)