Ytukyg

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(ncdot(2/3)ncdot(2/3)^2ncdot(2/3)^3ncdotsright).$$

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

Thanks!

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

$$dots Tleft(frac{2^{q-1}cdot n}{3^{q-1}}right)= Tleft(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:
$$Tleft(frac{2^qcdot n}{3^q}right)=T(1)Rightarrow left(frac23right)^qn=1Rightarrow n=left(frac{3}{2}right)^qRightarrow log_{frac32}n=q$$
$$Rightarrow T(n)=T(1)+lg^2 n+lg^2left(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^2left(left(frac{2}{3}right)^knright),quad q=log_{frac32}n$$
Now we have using some basic algebra and properties of the logarithms: $$left(lgleft(left(frac23right)^k cdot nright)right)^2=left(lgleft(frac23right)^k+ lg nright)^2=left(klgleft(frac23right)+ lg nright)^2=$$
$$=k^2 lg^2left(frac23right)+2klgleft(frac23right)lg n+lg^2n$$
$$Rightarrow T(n)=Theta(1)+lg^2left(frac23right)sum_{k=0}^{q-1}k^2+2lgleft(frac23right)lg nsum_{k=0}^{q-1} k +lg^2nsum_{k=0}^{q-1}1$$
$$=Theta(1)+lg^2left(frac23right)frac{(q-1)q(2q-1)}{6}+2lgleft(frac23right)lg nfrac{(q-1)q}{2}+lg^2 n (q-1)$$
Now note that $ displaystyle{q=log_{frac23}{n}=frac{lg n}{lgfrac23}},$ and to obtain the time complexity constants don't matter.
$$T(n)= Theta(1)+c_1 (lg n-1)lg n(2lg n-1)+c_2 lg ncdot (lg n-1)lg n +c_3 lg^2ncdot (lg n-1) $$
$$T(n)=Theta(1)+c_1Theta(lg^3 n)+c_2Theta(lg^3 n)+c_3Theta(lg^3n)=Theta(lg^ 3 n)$$

Look at the generaliyzed recurrence $Tleft(xright)=Tleft(ccdot xright)+left(log_{10}xright)^{2}$ with $0<c<1$.

First of all, $text{Dom}Tleft(xright)subseteqmathbb{R}^{+}$ as $log_{10}x$ existst and $text{Dom}log_{10}xsubseteqmathbb{R}^{+}$. Therefore, define $$U(x)=Tleft(10^{x}right)qquadlog_{10}c=alpha<0$$

Then:

$$Tleft(xright)=Uleft(log_{10}xright)qquad Tleft(cxright)=Uleft(alpha+log_{10}xright)$$

Therefore, for U, the functional equation becomes:

$$Uleft(vright)=Uleft(alpha+vright)+v^{2}$$
Let $v_{1}=-kalpha+beta$ with $betain(0,-alpha]$ and $k$ integer, then

$$Uleft(beta-kalpharight)=Uleft(beta-left(k-1right)alpharight)+left(beta-kalpharight)^{2}$$

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

$$Uleft(beta+kalpharight)=Uleft(beta+left(k-1right)alpharight)-left(beta-left(k-1right)alpharight)^{2}$$

$$U(v_{1})=sum_{i=1}^{k}left(beta-ialpharight)^{2}+Uleft(betaright)=beta^{2}k-alphabeta k(k+1)+frac{alpha^{2}}{6}k(k+1)(2k+1)+Uleft(betaright)$$

$$U(v_{2})=-sum_{i=0}^{k-1}left(beta-ialpharight)^{2}+Uleft(betaright)=beta^{2}k-alphabeta k(k+1)+frac{alpha^{2}}{6}k(k+1)(2k+1)+Uleft(betaright)$$

$$Uleft(beta-kalpharight)=beta^{2}k-alphabeta k(k+1)+frac{alpha^{2}}{6}k(k+1)(2k+1)+Uleft(betaright)$$

$$Uleft(beta+kalpharight)=-beta^{2}k+alphabeta k(k+1)-frac{alpha^{2}}{6}k(k-1)(2k-1)+Uleft(betaright)$$

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)=Tleft(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)$