How to solve $T(n) = T(2n/3) + \lg^2 n$ by substitution?

Question

My solution through substitution is as follows:

$$T(n) = T(2n/3) + \lg^2 (n)$$ $$T(2n/3) = T(4n/9) + \lg^2 (2n/3)$$ $$T(4n/9) = T(8n/27) + \lg^2 (4n/9)$$ And so on...

But my actual problem is how can I calculate the below step which cause to obtain order of the above expression:

$$\lg^2 \left(n\cdot(2/3)n\cdot(2/3)^2n\cdot(2/3)^3n\cdots\right).$$

Also I know the order is $\theta(\lg^3n)$.

Thanks!

Answer 1

$$T(n)=T\left(\frac{2n}{3}\right)+\lg^2 n$$ $$T\left(\frac{2n}{3}\right)=T\left(\frac{2\cdot\frac{2n}{3}}{3}\right)+\lg^2\left(\frac{2n}{3}\right)=T\left(\frac{2^2n}{3^2}\right)+\lg^2\left(\frac{2n}{3}\right)$$ $$T\left(\frac{2^2n}{3^2}\right)=T\left(\frac{2^3n}{3^3}\right)+\lg^2\left(\frac{2^2n}{3^2}\right)$$

$$\dots \ T\left(\frac{2^{q-1}\cdot n}{3^{q-1}}\right)=\ T\left(\frac{2^{q}\cdot n}{3^{q}}\right)+\lg^2 \left(\frac{2^{q-1}\cdot n}{3^{q-1}}\right) $$ Now in order to obtain $T(1)$ we consider the limit condition: $$T\left(\frac{2^q\cdot n}{3^q}\right)=T(1)\Rightarrow \left(\frac23\right)^qn=1\Rightarrow n=\left(\frac{3}{2}\right)^q\Rightarrow \log_{\frac32}n=q$$ $$\Rightarrow T(n)=T(1)+\lg^2 n+\lg^2\left(\frac{2n}{3}\right)+\dots +\lg^2 \left(\frac{2^{q-1}\cdot n}{3^{q-1}}\right) $$ Now we write the above as a sum. Also the time complexity of $T(1)$ is just $\Theta(1)$. $$T(n)=\Theta(1)+\sum_{k=0}^{q-1}\lg^2\left(\left(\frac{2}{3}\right)^kn\right),\quad q=\log_{\frac32}n$$ Now we have using some basic algebra and properties of the logarithms: $$\left(\lg\left(\left(\frac23\right)^k \cdot n\right)\right)^2=\left(\lg\left(\frac23\right)^k+ \lg n\right)^2=\left(k\lg\left(\frac23\right)+ \lg n\right)^2=$$ $$=k^2 \lg^2\left(\frac23\right)+2k\lg\left(\frac23\right)\lg n+\lg^2n$$ $$\Rightarrow T(n)=\Theta(1)+\lg^2\left(\frac23\right)\sum_{k=0}^{q-1}k^2+2\lg\left(\frac23\right)\lg n\sum_{k=0}^{q-1} k +\lg^2n\sum_{k=0}^{q-1}1$$ $$=\Theta(1)+\lg^2\left(\frac23\right)\frac{(q-1)q(2q-1)}{6}+2\lg\left(\frac23\right)\lg n\frac{(q-1)q}{2}+\lg^2 n (q-1)$$ Now note that $\ \displaystyle{q=\log_{\frac23}{n}=\frac{\lg n}{\lg\frac23}}\,$ and to obtain the time complexity constants don't matter. $$T(n)= \Theta(1)+c_1 (\lg n-1)\lg n(2\lg n-1)+c_2 \lg n\cdot (\lg n-1)\lg n +c_3 \lg^2n\cdot (\lg n-1) $$ $$T(n)=\Theta(1)+c_1\Theta(\lg^3 n)+c_2\Theta(\lg^3 n)+c_3\Theta(\lg^3n)=\Theta(\lg^ 3 n)$$

Answer 2

Look at the generaliyzed recurrence $T\left(x\right)=T\left(c\cdot x\right)+\left(\log_{10}x\right)^{2}$ with $0<c<1$.

First of all, $\text{Dom}T\left(x\right)\subseteq\mathbb{R}^{+}$ as $\log_{10}x$ existst and $\text{Dom}\log_{10}x\subseteq\mathbb{R}^{+}$. Therefore, define $$U(x)=T\left(10^{x}\right)\qquad\log_{10}c=\alpha<0$$

Then:

$$T\left(x\right)=U\left(\log_{10}x\right)\qquad T\left(cx\right)=U\left(\alpha+\log_{10}x\right)$$

Therefore, for U, the functional equation becomes:

$$U\left(v\right)=U\left(\alpha+v\right)+v^{2}$$ Let $v_{1}=-k\alpha+\beta$ with $\beta\in(0,-\alpha]$ and $k$ integer, then

$$U\left(\beta-k\alpha\right)=U\left(\beta-\left(k-1\right)\alpha\right)+\left(\beta-k\alpha\right)^{2}$$

Let $v_{2}=k\alpha+\beta$ with $\beta\in(0,-\alpha]$ and $k$ integer, then

$$U\left(\beta+k\alpha\right)=U\left(\beta+\left(k-1\right)\alpha\right)-\left(\beta-\left(k-1\right)\alpha\right)^{2}$$

$$U(v_{1})=\sum_{i=1}^{k}\left(\beta-i\alpha\right)^{2}+U\left(\beta\right)=\beta^{2}k-\alpha\beta k(k+1)+\frac{\alpha^{2}}{6}k(k+1)(2k+1)+U\left(\beta\right)$$

$$U(v_{2})=-\sum_{i=0}^{k-1}\left(\beta-i\alpha\right)^{2}+U\left(\beta\right)=\beta^{2}k-\alpha\beta k(k+1)+\frac{\alpha^{2}}{6}k(k+1)(2k+1)+U\left(\beta\right)$$

$$U\left(\beta-k\alpha\right)=\beta^{2}k-\alpha\beta k(k+1)+\frac{\alpha^{2}}{6}k(k+1)(2k+1)+U\left(\beta\right)$$

$$U\left(\beta+k\alpha\right)=-\beta^{2}k+\alpha\beta k(k+1)-\frac{\alpha^{2}}{6}k(k-1)(2k-1)+U\left(\beta\right)$$

Hence, we can define any function $U$ on $(0,-\alpha]$ and then extend it with the above formula. Implying $T $ from this is straightforward via the relation $U(x)=T\left(10^{x}\right)$. So in your case, you can have any function $f(x)$ on $\left(0,\log_{10}\frac{2}{3} \right]$, extend via the previously decribed relations, and set the function $T$ via $T(x)=U(\log_{10}x)$