I tried to solve the recurrence $T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$ with the master theorem but I can't get it to work.How many arrays exist in each step in the recursion tree?Or can I solve this problem some other way?Thanks.
$T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$
data structures;time complexity;recursion
At level 0, the top level, you'll have $1$ array, of size $n$.At level 1, you'll have $n^{1/2}$ arrays for each array at level $0$, for a total of $n^{1/2}$ arrays, each of size $n^{1/2}$.At level 2 you'll have $n^{1/4}$ arrays for each array at level 1 for a total of $n^{1/2}n^{1/4}$ arrays, each of size $n^{1/4}$.At level 3 you'll have $n^{1/8}$ arrays for each array at level 2 for a total of $n^{1/2}n^{1/4}n^{1/8}$ arrays, each of size $n^{1/8}$.In tabular form we have for the first few levels,$$\begin{array}{ccccc}\mathbf{level} & \mathbf{arrays} & \mathbf{size} & \mathbf{contribution/array} & \mathbf{total\ contribution}\\0 & 1 & n & n\lg n & (1)(n\lg n)=n\lg n\\1 & n^{1/2} & n^{1/2} & n^{1/2}\lg n^{1/2} & (n^{1/2})(n^{1/2}\lg n^{1/2})=n\lg n^{1/2}\\2 & n^{1/2}n^{1/4} & n^{1/4} & n^{1/4}\lg n^{1/4} & (n^{1/2}n^{1/4})(n^{1/4}\lg n^{1/4})=n\lg n^{1/4}\\3 & n^{1/2}n^{1/4}n^{1/8} & n^{1/8} & n^{1/8}\lg n^{1/8} & (n^{1/2}n^{1/4}n^{1/8})(n^{1/8}\lg n^{1/8})=n\lg n^{1/8}\end{array}$$So the total runtime, $T(n)$, will be the sum of the contributions at each level, namely$$n\lg n + n\lg n^{1/2} + n\lg n^{1/4} + n\lg n^{1/8} +\dotsb$$Use a property of the log function and you'll see that this simplifies to a simple expression.