Solutions to problems in recursion analysis

Click here for the questions

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

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

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

4 comments:

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

    ReplyDelete
  2. For problem 3:
    S(m) is O (m) not mlg(m).
    This makes T O(lg(n)).

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

    ReplyDelete