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.
On
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 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})$.