Solve the following Recurrence using Substitution(.ie Guess Method only)

Question

Solve using Substitution method for finding the upper bound

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

Answer 1

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

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

substituting 2 in 1 we get

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

T(n-2)=T(n-3)+1   ....4

Substituting 3 in 4

T(n)=T(n-3)+3

so on

T(n)=T(n-k)+k

Basis step is T(1)=1

n-k=1

k=n-1

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

T(n)= O(n)

Comments

Dear Sir this is iteration method

I want to solve it using substitution guess method

---

Don't call me sir

This is know as back substitution method,

If to want to guess here is an way,

we have an array of n element each time it is split in two array 1 and n-1 and amount of work done is 1

so after second iteration 2 and n-2 work done is 1

so on after n iteration n & 0

total work done is 1+1+1...n so O(n)

hope it help