edited by
1,201 views

2 Answers

Best answer
4 votes
4 votes
This is a simple question @Himanshu :)

Given , T(n) = T(n-1) + c

      ⇒   T(n) = (T(n-2) + c) + c [We substitute for T(n-1) similarly here]

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

     .

     .

      ⇒   T(n)  = T(n-n) + nc = T(0) + nc

     Considering T(0) = some constant , we have

     T(n)  =  nc  = O(n)
selected by
0 votes
0 votes

Time complexity = O(n)

Substitution Method Definition: Substituting the given function repeatedly until the given function is removed.

Related questions

5 votes
5 votes
1 answer
1
2 votes
2 votes
2 answers
3
1 votes
1 votes
1 answer
4
sripo asked Nov 14, 2018
1,570 views
T(n)=T(n/2)+2; T(1)=1when n is power of 2 the correct expression for T(n) is:a) 2(logn+1)b) 2lognc)logn+1d)2logn+1