-1
$\begingroup$

$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?

$\endgroup$
5
  • 5
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Feb 5, 2017 at 1:43
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Feb 5, 2017 at 1:51
  • $\begingroup$ @gnasher729 But, I cannot find any Theta (k^(n^2) * k) in my solution. Could you please clarify. $\endgroup$
    – New_Coder
    Commented Feb 5, 2017 at 2:01
  • $\begingroup$ @gnasher729 I think the answer is correct. Indeed, if $n = 2^k$ then $T(n) = n^{\log_2 n} (\log_2 n + T(1))$. $\endgroup$ Commented Feb 5, 2017 at 14:21
  • $\begingroup$ @New_Coder Should have been 2^(k^2). $\endgroup$
    – gnasher729
    Commented Feb 5, 2017 at 19:57

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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

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