Improving bound on recurrence T(n) = sum T(i)

48 Views Asked by At

Before I begin, I would like to clarify that this is part of a larger homework question.

We are told that the solution to a problem is $\Omega(2^n)$. Furthermore, the recurrence I have derived for the problem is:

T(n) = $\sum_{i = 1}^{n - 1} T(i) = T(1) + ... + T(n - 2) + T(n - 1) $$\geq 2 * T(n - 2)$ = $\Omega(2^{n/2})$

I am not sure how to tighten my bound on this solution to accommodate $2^n$. Any help is greatly appreciated!