# Recurrence Problem T(n) = 3T(n/3) + n

I am trying to get better at solving recurrence relations, so I am making my own simple relations and try to solve them. I have made the following recurrence: $$T(n) = 3T(\frac{n}{3}) + n$$

How can I solve $$T(n) = 3T(\frac{n}{3}) + n$$ using unfolding when $$T(1) = 1$$ ?

New contributor
Sonya is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• In addition to OmG's answer, keep in mind that unfolding is not a formal way to solve the recurrence. At some point in the unfolding you'll hand-wave by using dots and writing $T(n)$ as a function of $T(1)$. If you want a formal proof you'll need to use induction. (Or, in this case, you can just invoke the master theorem). – Steven Oct 9 at 12:40
• Adding a bit to @Steven, unfolding can be used to give you a guess for your induction proof. Most of the time this guess will be correct and the induction proof should flow easily with the result from unfolding. – ryan Oct 9 at 22:39

Using master theorem you can say it is $$\Theta(n\log n)$$. Also, try to expand the relation: $$T(n) = 3(3T(\frac{n}{3^2}) + \frac{n}{3}) + n = 3^2 T(\frac{n}{3^2}) + 2n$$ If you continue the above expansion, you will get that $$T(n) \sim n\log_3(n) = \Theta(n\log(n))$$.