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
Best Answer
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)$.