1

Given $T(n)$ is non-decreasing and $T(1)=7$, $$T(n) \leq 9T\left(\left\lfloor\frac{n}{3}\right\rfloor\right)+n$$ I am trying to show $$T(n) = O(n^2)$$

First, I used $$T\left(\frac{n}{3}\right) \leq 9T\left(\frac{n}{3^2}\right)+\frac{n}{3}$$

so

$$T(n) \leq 9^2 T\left(\frac{n}{3}\right)+n\left(1+\frac{9}{3}\right)$$

I kept doing it, so I get

$$T(n) \leq 9^kT\left(\frac{n}{3^k}\right)+n\cdot\sum_{j=0}^{k-1}{3^j}$$

I am confused on the next step. I used $k=\log_3(n)$ so

$$T(n) \leq 9^{\log_3(n)}T(1)+n\left(\frac{n-1}{2}\right)=7n^2+\frac{n^2}{2}-\frac{n}{2}$$

I think I am almost done, but I do I conclude that $$T(n) = O(n^2)$$?

Jochen
  • 2,260
Jayden Rice
  • 303

1 Answers1

2

You are done!

You have shown that $T(n)\leq 7.5n^2- 0.5n$. Hence, $0\leq\lim_{n\to\infty}T(n)/n^2 \leq 7.5$. Then by the definition of $O(1)$ you have $T(n)/n^2=O(1)$ or $T(n)=O(n^2)$. Hope it helps.

NaSa
  • 106