- 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)))

Technical & HR Interview Questions of Google,Microsoft,Yahoo and many more Companies.

### Solutions to problems in recursion analysis

Click here for the questions

Subscribe to:
Post Comments (Atom)

I was curious if there were solutions to problems 4-11? If so, where would they be?

ReplyDeletethanks a lot

ReplyDeleteFor problem 3:

ReplyDeleteS(m) is O (m) not mlg(m).

This makes T O(lg(n)).

I can't get #4.. what would it be? help please!

ReplyDelete