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