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.?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Название |
---|
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.