Given a recursive program with the following recurrence relation?

Question

Given a recursive program with the following recurrence relation: $$ \begin{array}{l} {C_n} = 3{C_{\frac{n}{3}}} + 1,n > 1\\ {C_1} = 1 \end{array} $$ Solve the recurrence relation to find the complexity of the program

I have a solution by placing sub-hidden as follows: $$ \begin{array}{l} {C_n} = 3{C_{\frac{n}{3}}} + 1\\ \Rightarrow {C_{{3^k}}} = 3{C_{{3^{k - 1}}}} + 1\\ \Leftrightarrow {C_{{3^k}}} = 3\left( {3{C_{{3^{k - 2}}}} + 1} \right) + 1 = {3^2}{C_{{3^{k - 2}}}} + 3 + 1\\ \Leftrightarrow {C_{{3^k}}} = {3^2}\left( {3{C_{{3^{k - 3}}}} + 1} \right) + 3 + 1 = {3^3}{C_{{3^{k - 3}}}} + {3^2} + 3 + 1\\ \Leftrightarrow {C_{{3^k}}} = ...\\ \Leftrightarrow {C_{{3^k}}} = {3^k}{C_1} + {3^{k - 1}} + ... + {3^2} + 3 + 1 = {3^k} + {3^k} - 1 = {3^{k}} +\frac{{{3^k} - 1}}{2}\\ {C_n} = \frac{{3n}}{2} - \frac{1}{2} \end{array} $$ Complexity of the program ${\rm O}(n)$

I want to ask everyone if there is any other solution method that directly uses integer values of $n$ without sub-implicit, a general solution

Answer 1

As

$$ C\left(3^{\log_3 n}\right) = 3C\left(3^{\log_3 \frac n3}\right) + 1 $$

making $\mathcal{C}(\cdot) = C\left(3^{(\cdot)}\right)$ and $z = \log_3 n$ we follow with

$$ \mathcal{C}(z) = 3\mathcal{C}(z-1)+1 $$

recurrence with solution

$$ \mathcal{C}(z) = 3^{z-1}c_0 + \frac 12(3^z-1) $$

now going backwards with $z = \log_3 n$ we have finally

$$ C(n) = \frac n3 c_0 +\frac 12(n-1) $$

or considering that $C(1) = 1$

$$ C(n) = \frac 12(3n-1) $$