Question

Can T(n) = 2T(n/2) + nlogn use master theorem?

Answer 1

I believe that we can use master theorem with this recurrence  T(n) = 2T(n/2) + nlogn

The provided recurrence is of the form T (n) = a T(n/b) + theta (n^k log^pn) where a>=1, b >1, k >=0, p is a real number, then: 

in your example the value of a=2 and b=2 and k=1, and this means that a is equal to b^k

the value of p  > -1, then T (n) = Theta (n^log_ba log ^p+1 n)

So, after applying the master theorem: 

T (n) = Theta ( n ^ log₂2 log ² n) => Theta (nlog²n )

Comments

The final time complexity T(n) = theta(n log^2 (n)) is correct!

---

It seems that the logn is a trivial component. so when applying the MT, the nlogn should be seen as n.
What about these recurrence relations?
T(n)=2T(n/2)+nlog(...log(n)),T(n)=2T(n/2)+nlog^k(n) (k is an arbitrary number)?

---

Regarding the first recurrence relation: T(n)=2T(n/2)+nlog(...log(n))
the time complexity should be: Theta (nlog^2(...log(n))). The second one, I think the time complexity should be: Theta (nlog^k+1(n).

---

I do not understand why this is theta(n log^2 n) and not theta(n log n)...

---

It is a straight up application of master theorem:

T(n) = 2 T(n/2) + n log^k(n).  

Solution is: T(n) = n log^(k+1) (n)

Or, if MT is not of interest, you can just do recursion tree unfolding and do the math that way.

Answer 2

I don't think that it could use master theorem. because n^(log(b)a) = n = O(nlogn), it seems that T(n) = Theta(nlogn). But before write this answer, we should check if f(n)/n^(log(b)a) = n^e, where e > 0. In this case f(n) = nlogn/n = logn = O(n^e), and it called polynomially smaller.

However, if you don't mean the master theorem mentioned in Instruction to Algorithms, it has a complete master theorem here, https://en.wikipedia.org/wiki/Master_theorem. You can use it :-)

Answer 3

Yes, we can use MT for this for sure. 

Comments

Then why T(n) = 2T(n/2) + n/logn can not use MT? In Wikipedia, I found this can not use MT. It says non-polynomial difference between f(n) and n^logba.

---

I'm also confused by why when f(n) = n logn, and n^log_b(a), MT can be applied, because f(n) / n^log_b(a) = log n != n^c, which means non-polynomial difference too.

---

Dear Prof, for T(n) = a T(n/b) + f(n), what would T(n) be if f(n) = Theta(n^c log^k n) while c > logb a, and k > 0? For example, T(n) = 2T(n/2) + n^2 log n.  I don't think this is discussed in case 3 in our textbook.

---

That is a good question.  You can post it as a new question, and we can all try to answer it!