# 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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 14, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.926251232624054, "perplexity_flag": "head"}