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$ ?

  • $\begingroup$ 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). $\endgroup$ – Steven Oct 9 '19 at 12:40
  • 1
    $\begingroup$ 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. $\endgroup$ – ryan Oct 9 '19 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))$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.