# Solving the recurrences of algorithms

Im having some trouble understanding recurrences.

I have an assignment where I have to solve some recurrences, theyre generally in the form of: $$T(n) = aT(n/b) + f(n)$$

I have 3 general formulas I can use:

1. If $f(n) = O(n^{\log_b a-\varepsilon})$ For some constant $\varepsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$

2. If $f(n) = \Theta(n^{\log_b a}lg^kn), k \ge 0$, then $T(n) =\Theta(n^{\log_b a}lg^{k+1}n)$

3. If $f(n) = \Omega(n^{\log_b a+\varepsilon})$ For some constant $\varepsilon > 0$, and satisfies the regulatory property, i.e. if $af(n/b) \le cf(n)$ for some constant $c < 1$ and all sufficiently large n, then $T(n) = \Theta(f(n))$

My problem is, I dont really understand how I'd use these to find the recurrence, or more specifically I dont know how to choose which formula to use...or maybe theres a simpler way of finding a recurrence

For example the questions I have are:

Solve the following recurrences:

1. $T(n) = 9T(\frac{n}{3}) + n^2lgn + 2n$

2. $T(n) = 3T(\frac{n}{2}) + n^2lg^3n$

3. $T(n) = 2T(\frac{n}{2}) + \sqrt{n}$

4. $T(n) = 3T(\frac{n}{3} + 5) + \frac{n}{2}$

Btw this isnt me asking for answers for my homework, those are just what I eventually need to solve.

-