Solutions to problems in recursion analysis

# Using the substitution method, we substitute the function recursively till we arrive at T(1).
i.e T(n)=T(n/2) + 1 = T(n/4) + 1 + 1 = ....

We get a total of lg(n) iterations
i.e T(n)=T(1) +lg(n)

Thus the complexity is O(lg n).

# Similar to the 1st problem, it takes lg(n) iterations to reach T(1).After final iteration:

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

Thus the complexity is (2^lg(n))*(lg n) = n*lg(n)

# Let n=2^m,then T(2^m)=2*T(2^m/2) + 1
Now let S(m)=T(2^m).
=>S(m)=2*S(m/2) +1

This is the same as 2nd problem.
Thus the complexity is O(m*lg(m)),but m=lg(n)

Thus the final complexity is O(lg(n)*lg(lg(n)))