0
$\begingroup$

Could someone help me with these 2 questions?

I do not understand the case 3

  1. $T(n) = T(n/2) + n \log n$

  2. $T(n)=T(n/8)+2 n$

$\endgroup$

closed as unclear what you're asking by Evil, David Richerby, xskxzr, Discrete lizard May 17 at 15:57

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Welcome to Computer Science! Could you please add some more detail to your question so as to narrow it a little bit? Bluntly stating "I do not understand the case 3" does not give potential answerers much to work with (except explaining the entire master theorem in detail). Also, please add any attempts you have made at solving the two questions so far. $\endgroup$ – dkaeae May 17 at 7:10
1
$\begingroup$

Let me show you how to solve these without using the master theorem. For the first item:

$$ T(n) = n\log n + \frac{n}{2} \log \frac{n}{2} + \frac{n}{4} \log \frac{n}{4} + \cdots \leq \left(n + \frac{n}{2} + \frac{n}{4} + \cdots\right) \log n \leq 2n\log n. $$ This shows that $T(n) = O(n\log n)$. Since clearly $T(n) = \Omega(n\log n)$, we can conclude that $T(n) = \Theta(n \log n)$.

The second item can be solved in the same way.

$\endgroup$

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