(n) = T(n-1) +n, T(0) = 0, T(1) = 1
T(n) = ?, 0(?) big-on ?
军:
T(n-2) +in-
(n) =T(n −1)+n » TCn 3) An 21-19 tới 1B)
= (T(n − 2) + n-1) + n
= (T(n − 3) + n-2) +n-1+n
= (T(n −4) + n-3) + n-2+n−1+n
. M
:NU2/5/231) T(n_n) +n+h-1th-2 +---+ |
= T(n − n) + 1+ 2+ 3+ + n
=0+1+2+ … + n
(1 + n)n
2
=
⇒ O(n²)
nunti)
2
= Ten)
= // 24² +12/201