Question

Consider the following recursive algorithm for computing the sum of the first n squares: S(n) = 12 +22 +32 +...+n2 . Algorithm S(n) //Input: A positive integer n //Output: The sum of the first n squares if n = 1 return 1 else return S(n − 1) + n* n a. Set up and solve a recurrence relation for the number of times the algorithm’s basic operation is executed. b. How does this algorithm compare with the straightforward non-recursive algorithm for computing this function?

Answer 1

Algorithm is

S(n)

{

if ( n==1 )

return 1

else

return S(n-1 ) + n*n

Now Let's first set The Recurrence Relation

As function have recursion and it is calling itself by passing n-1 elements only once

1.Lets say S(n) takes T(n) time then S(n-1) will take T(n-1) time

2. Along with recursion we have a constant c i.e. by If condition and one addition , multiplication operation in else

So we get Overall Recurrence As

T(n) = {

1 , when n=1

T(n-1) + c , when n>1

}

Note : Don't take S(n-1) + n*n as T(n-1) + n^2  because that n^2 apart from recursion means that there is some code that is taking n^2 units of time but in our case we didn't have such code we have only constants .

Hence we get the Recurrence relation

Now Lets Solve The Relation using Iterative method

T(n) = T(n-1) + c

= T(n-2) + c+ c= T(n-2) + 2c

= T(n-3 ) + c + 2c = T(n-3) + 3c

Observing the pattern after doing k times we get

T(n-k) + kc

Now assume n-k = 1 so k = n-1 we get

T(1) = 1

Now We have

1 + (n-1) c

= n.c = O(n)

c is the Time taken by all basic operations to run . We get n.c so it means that all basic operations are repeated n times .

So it The Time Taken by the recursive function S(n) is O(n)

Compare it with Non -Recursive approach

In Non- Recursive Algorithm

1. Take Value of n for user
2. Declare a sum variable that will store sum of all squares
3. Make a for loop that runs from 1 to n and add sum with i^2 = i*i

Time Complexity : As Loop is running for n times from 1 to n so all the statement inside loop also run for n times so all the basic basic operations are repeated n times .

In terms of Time Complexity we can use any of the approach either Recursive or Non-Recursive but in terms of writing and understanding non - recursive is always the best one .

So this is how we can analyze both approaches and then do the comparisons

Thank You

If u like the answer do Upvote it and have any doubt ask in comments