$T(n) = 3T(n/3) + c$ using substitution, geometric series

Question

so I have to find the asymptotic complexity of

$T(n) = 3Tn(n/3) + c$

using either the substitution method, a recursion tree or induction. I used the Master Theorem to find an answer, but can't use it to justify.

So I got n.

I decided to use substitution because we had not learned the other 2 methods yet. I got as far as finding

$k = \log_3 n$

and

$T(n) = 3^kT(n/3^k) + 3^{k-1} c + 3^{k-2} c + 3^{k-3} c + 3^{k-k} c$

and when substituted k in:

$T(n) = 3^{\log_3n}T(n/3^{\log_3n}) + 3^{{\log_3n}-1} c + 3^{{\log_3n}-2} c + 3^{{\log_3n}-3} c + 3^{k-k} c$

$T(n) = nT(1) + 3^{{\log_3n}-1} c + 3^{{\log_3n}-2} c + 3^{{\log_3n}-3} c + 3^{{\log_3n}-{\log_3n}} c$

But I'm stuck here with the geometric series and how to get the exponents to be correct...or what they are

would it be: $n/3^n$ ? The $-1, -2, -3$ , of the equation are confusing me

Answer 1

If you want to verify the geometric series, your series is (when written backwards):

$$T(n) = nT(1)+c\sum_{k=1}^{\log_3(n)}3^k.$$

Now use the fact that the above series is of order $3^{\log_3(n)}=n$. So $T(n)=O(n)$.

Answer 2

Your are close; you just have to sum the geometric series.

You have

$\begin{array}\\ T(n) =nT(1)+c\sum_{k =1}^{\log_3n}3^{\log_3 n - k}\\ =nT(1)+c\sum_{k =1}^{\log_3n}3^{\log_3 n}3^{ - k}\\ =nT(1)+c3^{\log_3 n}\sum_{k =1}^{\log_3n}3^{ - k}\\ =nT(1)+cn\sum_{k =1}^{\log_3n}3^{ - k}\\ \end{array} $

Now use $\sum_{k=1}^m x^k =x\frac{x^{m}-1}{x-1} $ or its equivalent $\sum_{k=1}^m x^{-k} =x^{-1}\sum_{k=0}^{m-1} x^{-k} =x^{-1}\frac{1-x^{-m}}{1-x^{-1}} $.

We get for the sum, with $x = 3$ and $m = \log_3 n$, $\sum_{k =1}^{\log_3n}3^{ - k} =\frac13\frac{1-3^{-\log_3 n}}{1-\frac13} =\frac{1-\frac1{n}}{2} $.

Combine these and you are done.

You really need to be able to sum a geometric progression, in all its various disguises. This is a basic tool in math and computer science, and if you have trouble doing this, please get help.