Solutions to Some Recurrences

 Master Theorem

 If F(n) = A*F(n/B) + D*n^C, where A > 0, B > 1, D > 0, and C >= 0, then

 F(n) = Theta(n^C) if C > log_B(A),

        Theta(n^C log n) if C = log_B(A),

        Theta(n^{log_B(A)}) if C < log_B(A).

 Note that C = log_B(A) is equivalent to B^C = A.

 Anti-Derivative Method

 If F(n) = F(n-1) + f'(n), then F(n) = Theta(f(n)).