Итак, нам дано это
O(T(n)), если T(n)=T(n−1)+3n+1 для n>0 и T(0)=1
O(T(n))
T(n)=T(n−1)+3n+1
n>0
T(0)=1
, и нам нужно определить нотацию Big-O для этого. Тем не менее, я пытался решить эту проблему, но у меня возникла проблема с константами, когда я попытался ее упростить. Любая помощь высоко ценится. Спасибо
O(n) = sum(i*3 + 1), 0 <= i <= n, которое может быть упрощено до
O(n) = sum(i*3 + 1), 0 <= i <= n
O(n) = n+1 + 3*sum(i), 0 <= i <= n после вычисления суммы мы получаем
O(n) = n+1 + 3*sum(i), 0 <= i <= n
O(n) = n+1 + 3*n(n+1)/2, затем переставляем условия, чтобы получить
O(n) = n+1 + 3*n(n+1)/2
O(n) = 3/2*n2 + 5/2*n + 1
Константы не имеют отношения к нотации Big-O. О (Т (п)) = О (Т (п-1)) + О (п).