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:
If $f(n) = O(n^{\log_b a-\varepsilon})$ For some constant $\varepsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$
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) $
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:
$T(n) = 9T(\frac{n}{3}) + n^2lgn + 2n$
$T(n) = 3T(\frac{n}{2}) + n^2lg^3n$
$T(n) = 2T(\frac{n}{2}) + \sqrt{n}$
$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.
