反復法によるT（n）= T（n-1）+（n-1）の解き方は？

Question

は、誰もがこれで私を助けることができるしてください： を使用して解く反復法T（N）= T（N - 1）+（N - 1）

そして証明するものT（n）が∈Θ（n²）

あなたが段階的に説明できる場合は、私は感謝します。十分大きな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 - 1)/3 ≤ T(n) ≤ n2 

したがって、我々はこのようT(n) = Θ (n²)、T(n) = Ω(n²) and T(n) = O(n²)を有します。