Consider the following algorithm:

int f(n)

/* n is a positive integer */

if (n<=4) return n

int sum=0

for i=1 to 3 do

sum = sum + ( i * f(n-i) )

for i=1 to n do

for j=n down to n-2 do

sum = sum + ( i * j )

return sum

Let T(n) be the time f(n) takes. Write a recurrence formula for T(n).