1

$$T(n) = nT(\sqrt{n}) + n^2, T(2) = 1$$

The master theorem does not apply here, only recursion tree. Assume $n = 2^{2^k}$.

The solution for self-check is $T(n = 2^{2^k}) = k \cdot n^2 + \frac{n^2}{4}$.

Edited:

My approach:

$T(2^{2^k}) = 2^{2^k}T(2^{2^{k-1}}) + 2^{2^{k + 1}}$

$= 2^{2^k + 2^{k - 1}}T(2^{2^{k-2}}) + 2^{2^{k+1}} + 2^{2^{k+1}}$

...

$=2^{\sum_{i = 1}^{k} 2^i} + k \cdot 2^{2^{k+1}}$

$=2^{\sum_{i = 0}^{k} 2^i - 1} + k \cdot 2^{2^{k+1}}$

$=2^{2^{k+1} - 2} + k \cdot n^2$

$=\frac{n^2}{4} + k \cdot n^2$

curiouscupcake
  • 231

1 Answers1

1

Let first rewrite the equation: $$T(n^2)=n^2T(n)+n^4$$

  • First step is to homogenize the formula.

Let set $T(n)=n^2U(n)$, after substitution we get $$U(n^2)=U(n)+1$$

  • Then we linearize it.

Let set $n=2^p$ and $V(p)=U(n)$, after substitution we get $$V(2p)=V(p)+1$$

Let set $p=2^q$ and $W(q)=V(p)$, after substitution we get $$W(q+1)=W(q)+1$$

  • Solve the formula (notice it is a telescoping sequence)

$$W(q)=W(0)+q$$

  • Last step is to go back up the chain of substitutions

$W(0)=V(2^0)=V(1)=U(2^1)=U(2)=\dfrac{T(2)}{2^2}=\dfrac 14$

$q=\log_2(\log_2(n))$

$T(n)=n^2U(n)=n^2V(p)=n^2W(q)=n^2(\frac 14+q)$

$$T(n)=\frac 14n^2 + n^2\log_2(\log_2(n))$$

zwim
  • 28,563