Define sn for n epsilon z be the recurrence sn 0 f n 1 s n2

Define s(n) for n epsilon z^+ be the recurrence: s(n) = {0 f n =1 s() n/2) + 1 if n greaterthanorequalto 2 prove that s(n) greaterthanorequalto lg (n) for all n greaterthanorequalto hence s(n) ohm (1 gn)

Solution

Answer:

It is nothing but :

S(n)=S(n/2)+1

and S(2)=1

Now using Master\'s theorm , we have

a = 1 , b = 2 , c = 0

loga base b = log1 base 2 = 0

therefore c = loga base b

therefore S(n) = omega( n^clog^k+1) = omega(n^0 log^0+1n) = omega(logn) ---proved