What can be an initial guess for finding the tight asymptotic bounds of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution method?

  • $\begingroup$ You can find the answer using the master theorem. $\endgroup$ Commented Sep 24, 2019 at 6:58
  • 3
    $\begingroup$ Hint, expand the sum on the right to get a closed form for $T(n)$. You can use the formula $\sum_{i = 0}^{n}i^2 = \frac{n (n+1)(2n+1)}{6}$. $\endgroup$ Commented Sep 24, 2019 at 8:14


Your Answer

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

Browse other questions tagged or ask your own question.