Question

Consider the following recursive algorithm

Algorithm S(n)

if n==1 return 1

else return S(n-1) + n*n*n

1)What does this algorithm compute?

2) Set up and solve a recurrence relation for the number of times the algorithm's basic operation is executed.

3) How does this algorithm compare with the non-recusive algorithm for computing thius function in terms of time efficeincy and space effeciency?

Answer 1

1. ) This algo. computes summation of (1^3 + 2^3+ 3^3 +...n^3) which is equal to {n*(n+1)/2}^2.

2.) Recurrence relation:

t(n) = t(n-1) + n*n*n

= t(n-2) + (n-1)^3 + n^3 = t(n-3) + (n-2)^3 + (n-1)^3 + n^3

= .. = t(n-k) + (n-k)^3 + ..+ (n-2)^3 + (n-1)^3 + n^3

= t(1) + 1^3 + 2^3 + ...+(n-2)^3 + (n-1)^3 + n^3

= {n*(n+1)/2}^2.

3.) Non-recursive algo, will have same time complexity that of recursive version. But recuresive algo. will have approx. n stack calls. So, space complexity will be of O(n) while in non-recursive case, it requires no extra variable therefore, space complexity will be O(1).

Hope it helps, do give your response.