Solving the recurrence relation $\mathcal{T}(n) = \sqrt{n}\text{ }\mathcal{T}(\sqrt{n}) + \mathcal{O}(n^{2}) $

37 Views Asked by At

Given Recurrence Relation $$\mathcal{T}(n) = \sqrt{n}\text{ }\mathcal{T}(\sqrt{n}) + \mathcal{O}(n^{2}) $$

Master Theorem doesn't apply here.

Tried using $n= 2^{k}$, but got stuck at $$\mathcal{T}(2^{k}) = 2^{k/2}\mathcal{T}(2^{k/2}) + \mathcal{O}(2^{2k})$$

Help me in proceeding.