1. Analysis of recursive algorithm. Consider the pseudo code of the following th

Question

1. Analysis of recursive algorithm. Consider the pseudo code of the following three algorithms for computing 2n, where n is a non-negative integer

Alg1(n);

if n == 0 then

return 1;

else return 2 * Alg1(n -1) ;

end

Alg2(n);

if n == 0 then

return 1;

else ;

return Alg2(n - 1) + Alg2(n - 1) ;

end

Alg3(n);

if n == 0 then

return 1;

else m = floor(n/2);

p = Alg3(m);

p = p * p;

if n%2 == 1

then return 2 * p;

else return p;

end

end

(a) Will all three algorithms correctly compute 2n ? Briefly justify your answer.

(b) Let A(n), B(n), and C(n) be the running time of the Algorithm: 1 ,Algorithm: 2 and Algorithm: 3 respectively, as a function of n. Write down the recurrence relations for A(n), B(n), and C(n).

Explanation / Answer

a) All 3 are correct.

All can be proved by induction.

Alg1:

Assume Alg1(n-1)=2^(n-1)

Then, Alg1(n)= 2xAlg1(n-1)= 2x2^(n-1)=2^n

Alg2:

Assume Alg2(n-1)=2^(n-1)

Then, Alg2(n)= Alg2(n-1)+Alg1(n-1)

Alg1(n-1)=2^(n-1) as proved earlier.

So, Alg2(n)= 2^(n-1) + 2^(n-1) =2^n

Alg3:

Assume for all m such that m<n, Alg3 returns 2^m.

Now Alg3(n),

if n is even, it returns: Alg3(n/2)x Alg3(n/2)=2^(n/2) x 2^(n/2) =2^n

If n is odd, it returns: 2x Alg3((n-1)/2)x Alg3((n-1)/2) = 2^n again, by induction hypothesis.

Note that all 3 base cases are satisfied as all 3 algorithms return 1 on getting 0 as input.

b) A(n)=1+A(n-1)

B(n)=B(n-1)+A(n-1)

C(n)=C(n/2)+1

(1 represents constant number of operations.)

A(n), B(n) and C(n) come out to be O(n) O(n^2) and O(logn) respectively.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.