Question

An algorithm has a running time like the following:

T(n) = T(n-1) + an + b; for n> 0 and a, b: the constant T(0) = 0

Determine the complexity of T(n)

Answer 1

T(n) = T(n-1) + an + b
we need to take an+b in asymptotic.therefore an+b is taken as O(n)
or theta(n)

now equation becomes T(n)=T(n-1)+n
use substitution method:
{T(n) = T(n-1) +n; for n> 0
T(0)=0}

T(n) = T(n-1) +n ---(1)   
T(n-1) = T(n-2) +n-1;
Substitute T(n-1) in equation (1) then
T(n)=T(n-2)+(n-1)+n-----(2)
T(n-2)=T(n-3)+(n-2) substitute T(n-2) in equation(2)then
T(n)=T(n-3)+(n-2)+(n-1)+n---(3)

T(n)=T(n-k)+(n-(k-1))+(n-(k-2))+------+(n-1)+n
assume n-k=0
therefore n=k
T(n)=T(n-n)+(n-n+1)+(n-n+2)+-------+(n-1)+n
T(n)=0+1+2+3+-------+(n-1)+n
T(n)=n(n+1)/2
T(n)=theta(n^2)