1 (a) Given the following function (in pseudo-code), with n as an input parameter and n is a positive number:

int function f(n)

{

if n <= 3 then return 0

else

{

sum=f(n-3)+f(n-2)+f(n-1)

for i=1 to n do

{

for j=1 to n do

{

sum=sum+i*j

}

}

}

return sum

}

Let T(n) be the time complexity of f(n). Write a recurrence relation for T(n). You do not need to solve the recurrence, but be precise in its definition.

1 (b) Show the recursion tree for the above algorithm for computing f(5). Obtain the value of f(5). Show all your derivations.