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.Master Thereom (because it's not in the form $aT(\frac{n}{b}) + f(n)$)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?
How to solve for recurrence with substitution or other methods?
asymptotics;recurrence relation
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)$.