# How to solve for recurrence with substitution or other methods? [duplicate]

Forgive me if I am new, I am trying to learn how to solve recurrences.

I have the following recurrence:

$$T(n) = 2 T(\lfloor\frac{n}{3}\rfloor) + \frac{1}{2} T(\lfloor\frac{2n}{3}\rfloor) + n^2 \text{ if } n>0$$

Now from my understanding is that I am not able to use the following methods.

1. Master Thereom (because it's not in the form $aT(\frac{n}{b}) + f(n)$)
2. Tree Method (because of the $\frac{1}{2} T$, you cannot have a node of $\frac{1}{2}$), please correct me if I am wrong.

So which leaves me with the following method:

Only the substitution method, but what I don't understand that is the fact that for the substitution method, you have to guess for the $f(n)$ to substitute into the recurrence.

So my question is, how does one select the correct $f(n)$ to substitute?

## marked as duplicate by Raphael♦Sep 23 '13 at 7:27

• @JohSteward You will almost never guess tight bounds (if you are after $\Theta$-bounds). You can, for instance, try $c_1 = \frac{1}{2^{100}}$ and $c_2 = 2^{100}$; that'll work just as well as $c_1=3$ and $c_2=4$. The additional information is lost as soon as you say $\Theta(\dots)$, anyway. (Disclaimer: finding tight bounds is interesting in itself.) – Raphael Sep 23 '13 at 17:23
Use the Akra-Bazzi theorem. Let $p$ be the solution to $2\cdot(1/3)^p + (1/2)\cdot(2/3)^p= 1$, namely $p = 1$. Compute $$S(n) = \int_1^n \frac{x^2}{x^{p+1}} \, dx = n-1= \Theta(n).$$ Then $T(n) = \Theta(x^p S(n)) = \Theta(n^2)$.