Can T(n) = 2T(n/2) + nlogn use master theorem?
时间: 2023-12-26 22:06:16 浏览: 33
Yes, we can use the master theorem to solve the recurrence T(n) = 2T(n/2) + nlogn.
The master theorem states that if a recurrence relation can be expressed in the form T(n) = aT(n/b) + f(n), where a >= 1 and b > 1 are constants, and f(n) is a function, then:
1. If f(n) = O(n^(log_b(a-ε))) for some ε > 0, then T(n) = Θ(n^(log_b(a))).
2. If f(n) = Θ(n^(log_b(a))), then T(n) = Θ(n^(log_b(a)) log n).
3. If f(n) = Ω(n^(log_b(a+ε))) for some ε > 0, and if a*f(n/b) <= c*f(n) for some constant c < 1 and sufficiently large n, then T(n) = Θ(f(n)).
In our case, we have a = 2, b = 2, and f(n) = nlogn. We can compute log_b(a) = log_2(2) = 1.
Now, we need to check which case applies to f(n) = nlogn.
Case 2: f(n) = nlogn = Θ(n^(log_b(a))) with p = 1.
Therefore, T(n) = Θ(nlogn log n).