cześć,
Czytam algorytmy i struktury danych i mam problem z udowodnieniem ze T(n) = 2T(n/2 + 17) + n = O(nlogn). Całość psuje mi to 17 z którym nie wiem co zrobic. Chodzi o to żeby to udowodnić metodą podstawiania.
0
0
Póki co poradziłem sobie tak:
Mamy rekurencję T(n) = 2T(n/2 +17) + n i mamy udowodnić, że asympotycznie jest równa O(nlogn), a więc że T(n) <= cnlogn dla c > 0.
Ja przyrównałem funkcję T(n) do c*(n-d)log(n-d) gdzie c > 0 i d > 0. I po prostu nie jestem pewien czy mogę w ten sposób rozumować. A oto moje obliczenia (zakładamy że log = logartym przy podstawie 2):
T(n) <= 2c(n/2-d + 17)log(n/2-d + 17) + n
= 2c*(n - 2d + 34)/2log[(n - 2d + 34)/2] + n
= c(n - 2d + 34)(log(n - 2d + 34) - log2) + n
= c(n - 2d + 34)log(n - 2d + 34) - c(n - 2d + 34) + n
<= cn*logn, dla c >= 1 i d >= 17