Quizzes and Repeated Substitution

I've been doing bad on the quizzes because it's difficult to stay on top of the material all the time.

Repeated substitution sounds complicated but I guess this just means substitute the formula until you see a pattern.

If T(n) + 2T(n/2) + n + 1

Then, T(2^k) = 2 T(2^k-1) + 2^k + 1

= 2 ( 2T(2^k-2) + 2^k-1 + 1) + 2^k + 1
= 2^2 T(2^k-2) + 2^k + 2 + 2^k + 1
.
.
.
= 2^kT(2^k-k) + k2^k + 2^k - 1
= n + n logn + n - 1
= nlogn + 2n - 1