# Logarithmic recursive functions

I've got the following recursive equation:

$$T(n)=T\biggl(\frac{n}{3}\biggr)+2\log(n)$$

Given that: $$T(1)=1.$$

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!!!

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