Как решить T (n) = T (n-1) + (n-1) методом итерации?

Question

Пожалуйста, кто может помочь мне с этим: Решить с помощью итераций метода Т (п) = Т (п - 1) + (п - 1)

И доказать, что Т (п) ∈Θ (n²)

Пожалуйста, если вы можете объяснить шаг за шагом, я был бы благодарен.

Answer 1

Я решил легко в пути:

T (n) = T (n - 1) + (n - 1)-----------(1) 
//now submit T(n-1)=t(n) 

T(n-1)=T((n-1)-1)+((n-1)-1) 
T(n-1)=T(n-2)+n-2---------------(2) 

now submit (2) in (1) you will get 
i.e T(n)=[T(n-2)+n-2]+(n-1) 
T(n)=T(n-2)+2n-3 //simplified--------------(3) 

now, T(n-2)=t(n) 
T(n-2)=T((n-2)-2)+[2(n-2)-3] 
T(n-2)=T(n-4)+2n-7---------------(4) 
now submit (4) in (2) you will get 
i.e T(n)=[T(n-4)+2n-7]+(2n-3) 
T(n)=T(n-4)+4n-10 //simplified 
............ 
T(n)=T(n-k)+kn-10 

now, assume k=n-1 

T(n)=T(n-(n-1))+(n-1)n-10 
T(n)=T(1)+n^2-n-10 
According to the complexity 10 is constant 

So , Finally O(n^2) 

Answer 2

 
T(n) = T(n - 1) + (n - 1) 
     = (T(n - 2) + (n - 2)) + (n - 1) 
     = (T(n - 3) + (n - 3)) + (n - 2) + (n - 1) 
     = ... 
     = T(0) + 1 + 2 + ... + (n - 3) + (n - 2) + (n - 1) 
     = C + n * (n - 1)/2 
     = O(n2) 

Следовательно, для достаточного большого n, мы имеем:

 
n * (n - 1)/3 ≤ T(n) ≤ n2 

Поэтому мы имеем T(n) = Ω(n²) and T(n) = O(n²), таким образом T(n) = Θ (n²).