# Solve using master method $T(n) = n · T(n/2) + n^{\log n}$ [closed]

$T(n)=n\displaystyle \cdot T\left(\frac{n}{2}\right)+n^{\log_{2}n}$.

$f(n) = n^{\log_{2}n}$

Number of leaves = $n^{\log_{a}b} = n^{\log_{2}n}$

CASE 2 (All level same)

$f(n) = \Theta(n^{\log_{b}a} {\log^{k}n})$

$f(n) = \Theta(n^{\log_{2}n} {\log^{0}n}),$ because $b = 2$, $a = n$, $k = 0$

Is $T(n) = \Theta(n^{\log_{2}n} {\log_{2}n)}$ correct?

• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. – D.W. Feb 5 '17 at 1:43
• Substitute n = 2^k. I think it's Theta (k^(n^2)) and not Theta (k^(n^2) * k). n * T (n/2) is too small. Of course I might be wrong. – gnasher729 Feb 5 '17 at 1:51
• @gnasher729 But, I cannot find any Theta (k^(n^2) * k) in my solution. Could you please clarify. – New_Coder Feb 5 '17 at 2:01
• @gnasher729 I think the answer is correct. Indeed, if $n = 2^k$ then $T(n) = n^{\log_2 n} (\log_2 n + T(1))$. – Yuval Filmus Feb 5 '17 at 14:21
• @New_Coder Should have been 2^(k^2). – gnasher729 Feb 5 '17 at 19:57

This recurrence cannot be solved with the master theorem, since the master theorem only applies to recurrences of the form $T(n) = aT(n/b) + f(n)$ where $a\geq1$ and $b>1$ are constants. Your recurrence is not of this form, so the theorem doesn't apply.

Let $T(n) = n⋅T(n/2) + n^{log_2n}$, and let $T(n) = (1 + C(n))·n^{log_2n}$.

Then $T(n) = n⋅(1 + C(n/2))·(n/2)^{log_2n - 1} + n^{log_2n}$

$T(n) = 2⋅(1 + C(n/2))·(n/2)^{log_2n} + n^{log_2n}$

$T(n) = (1 + C(n/2)) / 2^{log_2n - 1} ·n^{log_2n} + n^{log_2n}$

$T(n) = (1 + (1 + C(n/2)) / 2^{log_2n-1}) · n^{log_2n}$

$C(n) = (1 + C(n/2)) / 2^{log_2n-1} = (1 + C(n/2)) · (2/n)$

Clearly C(n) -> 0, therefore $T(n) = \Theta(n^{log_2n})$. Actually, the limit of $T(n) / n^{log_2n}$ is 1.

$n^{log_2n}$ grows so fast that n·T(n/2) cannot keep up with it. For T(n) to grow faster than $O(n^{log_2n})$, n·T(n/2) would have to grow faster, and it doesn't.

• Could you please elaborate on how $\lim_{x\to\infty}C(n) = 0$? – Travis Feb 5 '17 at 21:18
• Added a line to make it more obvious. – gnasher729 Feb 5 '17 at 22:08