retagged by
295 views

1 Answer

3 votes
3 votes
$T(n) = \sqrt n *T(\sqrt n) + n$

Divide both sides by n

$\frac{T(n)}{n} = \frac{T(\sqrt n)}{\sqrt n} + 1$

Let $G(n) = \frac{T(n)}{n}$

$G(n) = G(\sqrt n) + 1$

For simplisity let's assume n is power of 2. i.e. $n = 2^k$

Let $H(k) = G(2^k)$

$G(2^k) = G(2^{k/2}) + 1$

$H(k) = H(k/2) + 1$

It's known that $H(k) = lg(k)$

$G(2^k) = H(k) = lg(k)$

$G(n) = lg(lg(n))$

$T(n) = n*lg(lg(n))$

No related questions found