2

I would like to prove the solution to the recurrence equation $T(n) = \sum_{i=0}^{n-1}T(i) + n$ .

By manually drawing out the recursion tree, I think T(n) = O($2^n$). Indeed, assuming the same for T(n) and proving by induction for T(n+1) also works. But I am looking for a more stronger proof that does not involve the initial guess that T(n) = O($2^n$).

kronkman
  • 35

1 Answers1

4

From the recurrence equation, $$T(n) = T(n-1) + \left(\sum_{i-0}^{n-2}T(i) + (n-1)\right) +1 = 2T(n-1) +1$$ $$\Longrightarrow T(n)+1 = 2(T(n-1)+1)=...=2^{n-1}(T(1)+1)=2^{n-1}(T(0)+2)$$ $$\Longrightarrow \color{red}{T(n)= 2^{n-1}(T(0)+2) - 1}$$

NN2
  • 15,892