Geek asks and answers

Recursion Analysis in Algorithms

This is an old home problem from my class of algorithms. I have a solution to the problem, but even after repeated attempts, I don’t understand how to think in the right direction to come to a 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;
   }
}

For me, since h (N-1) is called multiple times in a while loop, the while loop should run as many times as h (N-1) returns. In addition, calling the function h (N-1) in a while loop will also happen many times. So, for me, I should get something like this:

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


1. T (N) - ,
2. T (N-1) * H (N-1), h (N-1) T (N-1), , H (N-1) . ( H (N-1) - , )
3. C * H (N-1) - while ( while H (N-1) .

, , - .

!

+3
2

, , while 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;
   }
}

:

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

, ? g (N) g (N-1) .

h (N). ? h (N) h (N - 1), h (N-1) . ( while) . , h (N), while. , :

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

, T(n) = H(n) + O(1). , :

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

, h (N) h (N-1) (, , )

enter image description here

+1

More articles:


All Articles