This question already has an answer here:

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?



marked as duplicate by Raphael Dec 6 '14 at 8:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Did you try expanding it using a recursion tree? This approach will work out. $\endgroup$ – Yuval Filmus Dec 5 '14 at 22:50
  • $\begingroup$ Of course you can't; the recurrence does not fit the form that the Master theorem admits. $\endgroup$ – Raphael Dec 6 '14 at 8:51

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.

  • $\begingroup$ thanks i trying to write the of this, bue beacuse in each step add one more n, its not clearly for me. how can i write the sum? $\endgroup$ – user11001 Dec 6 '14 at 9:54
  • $\begingroup$ @user3630497 See my edited answer. Does that help? $\endgroup$ – Rick Decker Dec 6 '14 at 16:50
  • $\begingroup$ yes its help , thanks, how much steps in sum if when n<20 = O(1) ? $\endgroup$ – user11001 Dec 6 '14 at 19:17
  • $\begingroup$ That would depend on where you stop. At $T(1)$? At $T(2)$? At any rate, how many times could you repeatedly take the square root until you would up at the base case. Certainly no more than 3, starting at $n=20$. $\endgroup$ – Rick Decker Dec 6 '14 at 19:57
  • $\begingroup$ i want to stop at T(10). so how much steps exsit in sum in this case? $\endgroup$ – user11001 Dec 6 '14 at 20:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.