What is the value of T(n) for the given recurrence relation

Question

T(n)=T(n/2)+2; T(1)=1

when n is power of 2 the correct expression for T(n) is:

a) 2(logn+1)

b) 2logn

c)logn+1

d)2logn+1

Comments

Option D

---

T(n)=T(n/2)+2

T(n/2)=T(n/4)+2

T(n/4)=T(n/8)+2

T(n)=T(n/8)+2+2+2

T(n)=T(n/(2³)) +3*2

T(n)=T(n/(2^k)) +k*2

Let 2^k=n i.e k=lg n

T(n)=T(n/(2^{lg n})) +lg n *2

T(n)=T(1)+ 2* lg n

Since T(1)=1

T(n)= 2*log₂n +1

---

option d with elimination method.

Answer 1

let n be 2^k

T(2^k )=T(2^k-1 )+2

put k=1 to get T(1)=1

T(2)=T(1)+2

T(2)=3 as T(1)=1

put n value as 2 in option D

2log2+1=3

Hence verified it will not satisfy any other option