[Solved]: How to solve for recurrence with substitution or other methods?

Problem Detail: 

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?

Asked By : Joh Steward

Answered By : Yuval Filmus

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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14543

3.2K people like this

 Download Related Notes/Documents