I've got the following recursive equation:
$$T(n)=T\biggl(\frac{n}{3}\biggr)+2\log(n)$$
Given that: $T(1)=1.$
What i already tried:
Going step by step back to the base case:
$$T(n)=T\biggl(\frac{n}{3}\biggr)+2\log(n)$$
$$T\biggl(\frac{n}{3}\biggr)=T\biggl(\frac{n}{9}\biggr)+2\log\biggl(\frac{n}{3}\biggr)$$
$$\Rightarrow T(n)=T\biggl(\frac{n}{9}\biggr)+2\log\biggl(\frac{n}{3}\biggr)+2\log(n)$$
$$T\biggl(\frac{n}{9}\biggr)=T\biggl(\frac{n}{27}\biggr)+2\log\biggl(\frac{n}{9}\biggr)$$
$$\Rightarrow T(n)=T\biggl(\frac{n}{27}\biggr)+2\log\biggl(\frac{n}{9}\biggr)+2\log\biggl(\frac{n}{3}\biggr)+2\log(n)$$
$$…….$$
So, We can say:
$$T(n)=T\biggl(\frac{n}{3^k}\biggr) + \sum^{\log_{3}(n)-1}_{i=0} 2\log\biggl(\frac{n}{3^i}\biggr)$$
For $T(1)=1$ (Base case) We require: $$T\biggl(\frac{n}{3^k}\biggr)=1\Rightarrow \frac{n}{3^k}=1 \Rightarrow k=\log_{3}(n)$$
Note: $k$ Is the number of recursive calls until we reach the base case $(T(1)=1)$ when the recursion ends, So:
$$T(n)=1+\sum^{k-1}_{i=0} 2\log\biggl(\frac{n}{3^i}\biggr)$$
$$\Rightarrow T(n)=1+2\sum^{k-1}_{i=0}\bigl(\log(n)-\log(3^i)\bigr)$$
$$\Rightarrow T(n)=1+2\left[(k-1)\log(n)-\sum^{k-1}_{i=0}i\log(3)\right]$$
Note that $\sum^{k-1}_{i=0}i=\frac{k(k-1)}{2}=\frac{k^2-k}{2}$, Hence:
$$\Rightarrow T(n)=1+2\left[(k-1)\log(n)-\frac{(k^2-k)\log(3)}{2}\right]$$
Here is what i've done so far, Note that $k=\log_{3}(n).$
My question: Is it correct to say that: $T(n)=O\bigl(\log^2(n)\bigr)$?
If i did any mistake, please correct me.
Thanks!!!
Best Answer
You made a small error,$$T(n)=1+2\left[\color{red}k\log(n)-\sum^{k-1}_{i=0}i\log(3)\right]$$but that doesn't change the asymptotic behaviour of $T(n)$, which is indeed $O(\log^2(n))$.