Solving recurrence

Question

Can anyone help me solving this recurrence? I don't see how I could use Master Theorem for this one and I couldn't find anything that would give me some idea how to do this. $$ T(n) = T(\lfloor{2n/3}\rfloor)+ n^2 $$

Answer 1

For lack of a better phrase, let's just do it. I omit the floor function because it doesn't affect the asymptotic.

So for some large $n$, we look at $T(n)$. It spits out $T(2n/3) + \color{#F01C2C}{n^2}$.

So now we need to understand $T(2n/3)$. It spits out $T(4n/9) + \color{#F01C2C}{\frac{4}{9} n^2}$.

Taking $T(4n/9)$ yields $T\left(\left(\frac{2}{3}\right)^3 n\right) + \color{#F01C2C}{\left(\frac{4}{9}\right)^2n^2}$.

Let's do one more. $T\left(\left(\frac{2}{3}\right)^3 n\right) = T\left(\left(\frac{2}{3}\right)^4 n\right)+\color{#F01C2C}{\left(\frac{4}{9}\right)^3n^2}$.

This keeps on going, and the total will be on the order of the sum of the bits in $\color{#F01C2C}{\text{red}}$, which is

$$\color{#F01C2C}{n^2 \left( 1 + \frac{4}{9} + \left(\frac{4}{9}\right)^2 + \ldots\right)} = \frac{n^2}{1 - \frac{4}{9}}$$

where I used a geometric series to do the final summation.