[Teoria złożoności] Rekurencja, podstawienia i dowód

[karguz]

Rozwiąż zależność metodą podstawienia i udowodnij indukcyjnie:

1.
\(\displaystyle{ T(1) = 1}\)
\(\displaystyle{ T(n) = T(n - 1) + n}\) dla \(\displaystyle{ n > 1}\)

2. \(\displaystyle{ T(1) = 0}\)
\(\displaystyle{ T(n) = T(n/2) + 1}\) dla parzystego \(\displaystyle{ n > 1}\)
\(\displaystyle{ T(n) = T((n + 1)/2) + 1}\) dla nieparzystego \(\displaystyle{ n > 1}\)

W zadaniu 2 wystarczy, że uzyskasz
rozwiązanie dla \(\displaystyle{ n=2^k}\)
i naturalnego \(\displaystyle{ k}\).

Nie rozumiem metody podstawiania, a chcę ją zrozumieć. Nie wiem za bardzo co robić. Proszę o wytłumaczenie na podanych przykładach i z góry dziękuję bardzo.

[bartek118]

To znaczy, że po prostu podstawiasz i podstawiasz, i podstawiasz:
\(\displaystyle{ T(n) = T(n-1) + n = T(n-2) + (n-1) + n = T(n-3) + (n-2) + (n-1) + n = T(n-4) + (n-3) + (n-2) + (n-1) + n}\)
aż zobaczysz jakąś zależność, w tym wypadku:
\(\displaystyle{ T(n) = T(2) + 3 + \ldots + (n-1) + n = T(1) + 2 + 3 + \ldots + (n-1) + n = 1 + 2 + 3 + \ldots + (n-1) + n = \frac{(n+1)n}{2}}\)
Teraz pozostaje tylko dowód indukcyjny.