Q4. [4] answer questions for the following algorithms:

int foo(int n) {

if (n < =0) {return 0;}

return n + foo(n 1); }

1. [2] Show the recurrence relation of the time function T(n) for the above recurrence algorithm.

2. [2] Use a master method to solve the T(n). You need to show clear steps to justify your answers.