New answers tagged

0

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


0

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


Top 50 recent answers are included