How can this relation : $$ T(n)=4^n + 12 \cdot \sum^{n-2}_{i=1}{T(i)} $$ $$ T(1) = 1 $$

be evaluated to asysmtotic bound (Big O notation)?

It could be easy if the upper bound of the sum were n-1, but it is not.

  • $\begingroup$ You can always add extra non-negative terms on the RHS, if that helps. Whether the bound will be asymptotically tight is a different question. But nevertheless, you would get an upper bound. $\endgroup$
    – codeR
    May 15 at 10:47
  • $\begingroup$ $T(1)$ should be $O(1)$ to be consistent with the recurrence. $\endgroup$
    – codeR
    May 15 at 10:50
  • $\begingroup$ How is adding extra terms helpful here? $\endgroup$ May 15 at 10:51
  • 1
    $\begingroup$ $T(n) \le 4^n + 12\sum\limits_{i=1}^{n-1} T(i)$, then, as per your claim, it is comparably easy to solve! $\endgroup$
    – codeR
    May 15 at 12:34


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.