# Recurrence k-th pattern

I am trying to solve this recurrence $$T(n) = 6 T(\frac{n}{3}) + n$$.

1st recurrence: $$6^2T(\frac{n}{3^2}) + \frac{6n}{3} + n$$

2nd: $$6^3T(\frac{n}{3^3}) + \frac{6^3n}{3^2} + n$$

3rd: $$6^4T(\frac{n}{3^4}) + \frac{6^6n}{3^3} + n$$

I am having trouble describing the general pattern after the k-th iteration.

• Please define $n$, the range it covers, what is $n/3$ for instance if $n$ is integer (but not divisible by three), and what is the k in the title / in the k-th iteration? Do we need to get a formula for $T(n)$ in terms of $T(n/3^k)$ (or in terms of $T(n/3^{k+1})$? Nov 24, 2018 at 0:46
• Assume base case T(1) = 1. We need to get the general pattern for T(n) after the k-th iteration, for example T(n) = 6^k T(n/3^k) + ... Nov 24, 2018 at 0:59

I assume you are looking to find $$T(n)$$ after K iterations. First $$T(n) = 6 T(n/3) + n$$ then rewriting $$T(n/3)$$ in terms of $$T(n/3^2)$$ we conclude: $$T(n) = 6^2 T(n/3^2) + 6n/3 +n$$ similarly $$T(n)$$ after K iterations becomes: $$T(n) = 6^K T(n/ 3^K) + \sum_{i=1} ^K 6^{i-1}n/3^{i-1}$$ or $$T(n) = 6^K T(n/ 3^K) + (2^{K}-1)n$$

• If you rewrite T(n/3^2) in terms of T(n/3^3), then wouldn't it be: T(n) = 6^3T(n/3^3) + 37n Nov 24, 2018 at 4:44
• It would be $6^2 (6T(n/3^3) + n/3^2) + 6n/3 + n = 6^3T(n/3^3) + 7n$ Nov 24, 2018 at 7:09

If you are trying to solve the recurrence, try finding the initial pattern and the number of terms - this will help solve the equation in most of the cases.

In the first step, we have $$n$$ work to do, we do $$n$$ work and have 6 problems of the same type but of size $$\frac{n}{3}$$ this time.

In the second step, we have $$\frac{n}{3}$$ work to do, we do $$\frac{n}{3}$$ work and have 6 problems of the same type but of size $$\frac{n}{9}$$ this time. We have 6 problems of this type.

In the third step, we have $$\frac{n}{9}$$ work to do, we do $$\frac{n}{9}$$ work and have 6 problems of the same type but of size $$\frac{n}{27}$$ this time. We have 6 problems of this type.

This gives the equation,

$$T(n) = n + 6(\frac{n}{3}) + 36 (\frac{n}{9}) + 216(\frac{n}{27}) + ... +$$

$$T(n) = n + 2n + 4n + 8n + ...$$

You will have $$log_{3}n$$ such terms, as you are cutting down the problem size by a factor of three all the time. This is a sum of a geometric series, given the number of terms and common ratio, it is easy to sum.

$$T(n) = n + 2n + 4n + 8n + ... + 2^{log_{3}n}n$$

Kth term will be of the form $$2^{k}n$$.

The solution should be $$\Theta(n^{log_{3}6})$$.

• You did not remember to specify the initial condition (it is not very important though). Nov 24, 2018 at 0:47
• I'm trying to get the k-th form for the entire equation i.e. T(n) = 6^k T(n/3^k) + ... Nov 24, 2018 at 0:58
• Sorry, but your question reads "I am trying to solve this recurrence...". Nov 24, 2018 at 1:07