Tag Info

For $n > 0$ we have $$\frac{T(n)}{n} = \frac{T(\sqrt{n})}{\sqrt{n}}+c\frac{\ln n}{n}$$ calling $R(n) = \frac{T(n)}{n}$ we follow with $$R(n) = R(\sqrt{n})+c\frac{\ln n}{n}$$ but now $$R\left(2^{\log_2 n}\right) = R\left(2^{\log_2 \sqrt{n}}\right)+c\frac{\ln n}{n}$$ Calling now $\mathcal{R}(\cdot) = R\left(2^{(\cdot)}\right)$ and $z = \log_2 n$ we ...
As $$T\left(3^{\log_3n}\right)=3T\left(3^{\log_3 \sqrt[3]{n}}\right)+n^3$$ making $\mathcal{T}\left(\cdot\right)= T\left(3^{(\cdot)}\right)$ and $z= \log_3 n$ we follow with $$\mathcal{T}\left(z\right)= 3\mathcal{T}\left(\frac z3\right)+3^{3z}$$ now with an analog procedure, making $\mathbb{T}\left(\cdot\right)=\mathcal{T}\left(3^{(\cdot)}\right)$ and \$\...