T(n)= c1 nếu n=0. Ngược lại T(n) = T(n-1)+c2 nếu n>0
Quá trình hồi quy kết thúc khi n-i=0 <=> n=i;
thế n=i vào phương trình đệ quy ta được
Vậy T(n)=O(n).
Code:
T(n)=T(n-1)+c2
=[T(n-2)+c2]+c2=T(n-2)+2c2
=[T(n-3)+c2]+2c2=T(n-3)+3c2
....
=T(n-i)+ic2.Quá trình hồi quy kết thúc khi n-i=0 <=> n=i;
thế n=i vào phương trình đệ quy ta được
Code:
T(n)=T(0)+nc2
=c1+nc2Vậy T(n)=O(n).