Given a recursive program with the following recurrence relation?

[kan]

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 + 1}} - 1\\
{C_n} = 3n - 1
\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

 

[Cubist]

Your expression for C_n is incorrect. Using the recurrence relation gives C₃=4, C₉=13, but your expression yields C₉=3*9-1=26

I tried to work out where you went wrong. Here's one mistake (although you're kind-of close!)...

[math] \sum_{t=0}^{k-1}{3^t} \ne 3^k-1[/math]

 

[JeffM]

[MATH]C_3 = 3 * C_{3 \div 3} + 1 = 3 * C_1 + 1 = 3 * 1 + 1 = 4 \ne 8 = 9 - 1 = 3 * 3 - 1.[/MATH]
[MATH]n > 1 \text { and } n = 3^k \implies k > 0 \text { and } \dfrac{n}{3} = 3^{k-1}.[/MATH]
[MATH]\therefore C_n = 3C_{n \div 3} + 1 = 3^1C_{3^{k-1}} + 3^0.[/MATH]
For example,

[MATH]C_3 = 3 * 1 + 1 = 4.[/MATH]
[MATH]C_9 = 3 * 4 + 1 = 13.[/MATH]
[MATH]C_{27} = 3 * 13 + 1 = 40.[/MATH]
This gives us some tests for checking a solution.

 

[JeffM]

Your expression for C_n is incorrect. Using the recurrence relation gives C₃=4, C₉=13, but your expression yields C₉=3*9-1=26

I tried to work out where you went wrong. Here's one mistake (although you're kind-of close!)...

[math] \sum_{t=0}^{k-1}{3^t} \ne 3^k-1[/math]

And [MATH]3^k + 3^k - 1 = 2 * 3^k - 1 \ne 3^{(k+1)} -1 [/MATH]

 

[JeffM]

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 + 1}} - 1\\
{C_n} = 3n - 1
\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

This problem has been bothering me a lot.

Ignoring the algebraic errors, which of course can be fixed, I do not think the proposed method can work at all.

The fundamental problem is here:

[MATH]\implies {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\\ \implies {C_{{3^k}}} = ...\\ \implies {C_{{3^k}}} = {3^k}{C_1} + {3^{k - 1}} + ... + {3^2} + 3 + 1[/MATH]Those dots are supposed to represent a sum with some unspecified number of terms, but presumably it is in terms of k. But, in general, k will not be an integer. A number of terms that is not an integer makes no sense to me.

I can make the method work only for a very restricted set of special cases. Here goes:

[MATH]\text {Given: } m \text { is an integer} > 1,\ n = 3^m,\ c_1 = 1,\text { and } c_n = 3c_{n/3} + 1.[/MATH]
Let's say m = 3. So n is 27.

[MATH]c_{27} = 3c_{27/3} + 1 = 3^1c_9 + 3^0 = 3^1c_9 + \sum_{j=0}^0 3^j =[/MATH]
[MATH]3^1(3c_{9/3} + 1) + \sum_{j=0}^0 3^j = 3^1(3c_3 + 1) + \sum_{j=0}^0 3^j = 3^2c_3 + \sum_{j=0}^1 3^j =[/MATH]
[MATH]3^2(3c_{3/3} + 1) + \sum_{j=0}^1 3^j = 3^2(3c_1 + 1) + \sum_{j=0}^1 3^j =[/MATH]
[MATH]3^2(3 * 1 + 1) + \sum_{j=0}^1 3^j = 3^3 + 3^2 + \sum_{j=0}^1 3^j = \sum_{j=0}^3 3^j.[/MATH]
The expression has 4 terms. It is obvious (and can be proved by induction) that

[MATH]c_n = \sum_{j=0}^m 3^j = \dfrac{3^{(m+1)} - 1}{2}.[/MATH]
And we have already shown that

[MATH]c_{3^1} = 4 = \dfrac{3^2 - 1}{2},\ c_{3^2} = 13 = \dfrac{3^3 - 1}{2}, \text { and } c_{3^3} = 40 = \dfrac{3^4 - 1}{2}.[/MATH]
But I do not see how that method can be extended to other multiples of 3, let alone integers that are not even divisible by 3.

Purely negative results.