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!

Answer 1

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)

Answer 2

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)