-1
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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$ Commented Oct 9, 2019 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$ Commented Oct 9, 2019 at 22:39

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.