T(n) = 2*T(n/2) + n*log(n)
I tried to solve it using master method but it doesn't seem to fit any of the three cases.
Am I correct.?
# | User | Rating |
---|---|---|
1 | tourist | 3856 |
2 | jiangly | 3747 |
3 | orzdevinwang | 3706 |
4 | jqdai0815 | 3682 |
5 | ksun48 | 3591 |
6 | gamegame | 3477 |
7 | Benq | 3468 |
8 | Radewoosh | 3462 |
9 | ecnerwala | 3451 |
10 | heuristica | 3431 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | -is-this-fft- | 162 |
3 | Dominater069 | 160 |
4 | Um_nik | 158 |
5 | atcoder_official | 156 |
6 | Qingyu | 155 |
7 | djm03178 | 151 |
7 | adamant | 151 |
9 | luogu_official | 150 |
10 | awoo | 147 |
Name |
---|
T(n) = 2*T(n/2) + n*log(n)
T(n) = 4*T(n/4) + n*log(n/2) + n*log(n)
T(n) = 8*T(n/8) + n*log(n/4) + n*log(n/2) + n*log(n)
...
So we can see the sum is of order n*log2(n).
The very question has been explained. Its mentioned that:
"The master method does not apply to the recurrence
T(n) = 2T(n/2) + n lg n,
even though it has the proper form: a = 2, b = 2, f(n) = n lg n, and . It might seem that case 3 should apply, since f(n) = n lg n is asymptotically larger than . The problem is that it is not polynomially larger. Consequently, the recurrence falls into the gap between case 2 and case 3 of master theorem."
The recurrence relation is n*(log 2n)
And the assumption that the gap between case 2 and case 3 is dependent on k isn't correct if I have understood you properly. The generalisation I mentioned only applies to cases when f(n) = Θ(nlogbalogkn) and doesn't cover other variants of f(n) being not asymptotically equal to nlogba and neither polynomially larger nor polynomially smaller.