# Solving using the master theorem: T(n)=T(n/2)+n⋅log n and T(n)=T(n/8)+2.n [closed]

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

## 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.

• 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. – dkaeae May 17 at 7:10

$$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)$$.