Analyzing recursion in algorithms

Question

This is an old homework problem from my algorithms class. I have the solution to the problem, but even after repeated attempts, I fail to understand how to think in the right direction to arrive at the solution.

function h(N) {
    if (N==1) return 3;
    else { 
        sum = 1;
        i = 0;
        while (i < h(N-1))
            sum = sum + i;
            i = i + 1;
        return sum;
   }
}

According to me, since h(N-1) is called repeatedly in the while loop, the while loop should run as many number of times as what is returned by h(N-1). Besides that, the function call h(N-1) in the while loop will also happen that many number of times. Thus, according to me, I should get something like this:

T(N) = T(N-1)*H(N-1) + C*H(N-1) + D

where
1. T(N) is the running time,
2. T(N-1)*H(N-1) because the one recursive call to h(N-1) will take T(N-1) and since it's recomputed every time the comparison is made, it will be called H(N-1) times. (where H(N-1) is the value returned from the call)
3. and C*H(N-1) is the running time for the statements inside the while loop (since the while loop runs H(N-1) times.

I did not get a satisfactory answer from my professor and I would appreciate if someone could help me understand this.

Thank you!

rrufai · Accepted Answer · 2012-05-13 12:13:54Z

2

Try understanding this in two steps, first consider this simpler function, where we replace the while loop with an if.

function g(N) {
    if (N==1) return 3;
    else { 
        sum = 1;
        i = 0;
        if(i < g(N-1))
            sum = sum + i;
            i = i + 1;
        return sum;
   }
}

Here, we get the recurrence:

G(N) = G(N-1) + O(1)

So far, so good? Here, the work to compute g(N) involves solving the smaller problem g(N-1) plus a constant amount of work.

Now, let's go back to the original function h(N). What has changed? Now, the work to compute h(N) involves solving the subproblem h(N - 1), h(N-1) times. And in each of those times (i.e. in the while loop), we do a constant amount of work. There is also another constant amount of work that is done only once in h(N), i.e. out of the while loop. So, we essentially get:

H(N) = H(N - 1) *{H(N - 1) + O(1)}  + O(1)

We can rewrite the above by making the substitution T(n) = H(n) + O(1). Thus, we get:

T(N) = H(N - 1) * T(N - 1)  + O(1)

edited May 13, 2012 at 12:13

answered May 13, 2012 at 11:46

rrufai

1,49514 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Shobit Over a year ago

Thanks! That was really helpful. I realized the way I thought of it that gave me T(N) = T(N-1)*H(N-1) + CH(N-1) + D is in fact the same equation that you mentioned T(N) = T(N-1) * H(N-1) + O(1) since CH(N-1) + D is a constant. Thanks for the clear explanation!

Jack · Accepted Answer · 2012-05-12 08:45:43Z

1

Assume that in executing h(N), the value of h(N-1) is recomputed at each iteration of the loop (which is probably the case for most languages and most compilers)

enter image description here

answered May 12, 2012 at 8:45

Jack

5,85812 gold badges52 silver badges76 bronze badges

4 Comments

Shobit Over a year ago

Thanks, but that solution is what I already have from my professor. If you could explain to me how to get the equation (especially the second term C * T(N-1) ), that would be more helpful.

amin k Over a year ago

@Shobit : c* h(n-1) is true or cT(n-1)...i think that ch(n-1) is true... and where is the answer is not clear? ( i am sorry,i can not speak English very well)

Shobit Over a year ago

Thanks for replying, amin k. The answer that I have is exactly what Jack has posted above as his reply (with the addition of the line "where C and D are constants" which is quite obvious).

Jack Over a year ago

@Shobit I think you should repost your question at programmers.stackexchange.com or math.stackexchange.com since it is more likely they have the expertise you are looking for.

Collectives™ on Stack Overflow

Analyzing recursion in algorithms

2 Answers 2

1 Comment

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related