How to solve this Recurrence ?

Question

T(n) = $\sum_{0}^{n-1}$ T(i) + cn

Comments

If you do not know to solve, start from 0, and numerically substitute the values. This will work for objective exams and never gives wrong.

---

@arjun sir , it is the recurrence of your question https://gateoverflow.in/208/what-is-the-time-complexity You got T(2) as 5. I am not able to understand . Could you pls explain how to solve this using back substitution

---

I do not think that is back substitution. That method is just enumeration. For simplicity, assume c = 1.

T(0) = 1.

T(1) = T(0) + 1 = 2

T(2) = T(0) + T(1) + 2 = 5

and so on.. Then check options. Quick way for objective exams and no chance of negatives.

Answer 1

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

Ans)  O(n^2)

Comments

O( 2^n ) is given answer !