Could someone please figure out the first picture by inducti

Could someone please figure out the first picture by induction and the rest using the substitution method for reccuralance relations I\'m really stuck :(

Solution

17.17: Substitution Method

T(N) = . T(N/2) +1

Substitute N by N/2 we get
T(N/2) = . T(N/4) +1

So Equation becomes

T(N) = T(N/4) + 1 + 1

Substitute N by N/4 we get
T(N/4) = . T(N/8) +1

So Equation becomes
T(N) = T(N/8) + 1 + 1 + 1

Like this it will continue , Till we reach T(1) , When we will reach T(1) let it be k , so

When N/2^k = 1
=> N= 2k
=> k = log n


So ,

T(N) = T(1) + 1 + 1 + 1 +1 + 1...log n times

1 will appear log n times

So Summation from 1 to log N that too 1 is Log N

that is we have log n number of 1s

So T(N) = O( Log N)