Consider the following algorithm(in java)

Algorithm

foo(n)

if n = 0 then return 1

else { x 0

for i 1 to n do x x + x/i

x x + foo(n 1)

return x }

The time complexity of this algorithm is given by the following recurrence equation:

f(0) = c1

f(n) = f(n 1) + c2n + c3, for n > 0

where c1, c2, and c3 are constants. Solve the recurrence equation and give the value of f(n) and its order using big-Oh notation. You must explain how you solved the recurrence equation