I am recently learning the how to use the various methods to solve recurrences. So far I have acquainted myself with the Master's Theorem and Substitution method. One method I just can't seem to understand is the following question which needs to be solved by characteristic equation:

$$ T(n) = 2T(n/3) + 1,T(1) = 1$$

I watched certain tutorials and readings and I imagine I needed to derive some sort of degree and simultaneous equation out of this?

How do I do it in this case?

Sorry for being amateur at this.

New contributor
eglades is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • $\begingroup$ Are you sure it needs to be solved by characteristic equation only? $\endgroup$ – Beyond Infinity 2 days ago

Write $n=3^m$ so $T(3^m)=2T(3^{m-1})+1$.

Then let $T(3^m)=u(m)$ so $u(m)=2u(m-1)+1$.

You should be able to solve this.


Your Answer

eglades is a new contributor. Be nice, and check out our Code of Conduct.

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.