Answering questions about the recurrence of certain aspects of an algorithm

Question

I am thoroughly confused by a problem that was brought up in class:

Given the following pseudocode for a function RANDOM which generates a random number based off of recursion:

function RANDOM(n)
1.  if n = 1 then
1.1     return 1
1.2 else
2.1     assign x = 0 with probability 1/2, or
2.2     assign x = 1 with probability 1/3, or
2.3     assign x = 2 with probability 1/6
3.      if x = 0 then
3.1         return (RANDOM(n-1) + RANDOM(n-2))
3.2     end-if
4.      if x = 1 then
4.1         return (RANDOM(n) + 2*RANDOM(n-1))
4.2     end-if
5.      if x = 2 then
5.1         return (3*RANDOM(n) + RANDOM(n) + 3)
5.2     end-if
6.  end-if
end-RANDOM

Answer the following three questions:

1. Give the recurrence equation for the expected running time of RANDOM.

2. Give the exact recurrence equation for the expected number of recursive calls expected by a call to RANDOM(n).

3. Give the exact recurrence equation for the expected number of times the return statement at line 5.1 is executed, in all calls to RANDOM(n), recursive or not.

Our professor gave us a version of this pseudocode that goes like this:

function RANDOM(n)
1.  if n = 1 then
1.1     return 1
1.2 else
2.1     assign x = 0 with probability 1/3, or
2.2     assign x = 1 with probability 1/3, or
2.3     assign x = 2 with probability 1/3
3.      if x = 0 then
3.1         return (RANDOM(n))
3.2     end-if
4.      if x = 1 then
4.1         return (RANDOM(n-1) + 1)
4.2     end-if
5.      if x = 2 then
5.1         return (3*RANDOM(n-1) + RANDOM(n-1) + 1)
5.2     end-if
6.  end-if
end-RANDOM

And answered the three questions as follows:

1)

T(n) = expected running time of RANDOM

$$ T(1) = 1 $$

$$ T(n) = 1 + \frac{T(n)}{3} + \frac{T(n-1)}{3} + \frac{T(n-1) + T(n-1)}{3} $$

which, after some algebra, comes out to equal:

$$ T(1) = 1 $$

$$ T(n) =\frac 32 * T(n-1) + 1, $$ , where $n>=1$.

I have one question about the answer to this problem. Why does the constant $1$ in the original equation not matter to the equation? Is it because it is being lumped in with constant time?

2)

R(n) = the expected number of recursive calls executed by a call to RANDOM(n). $$ R(1) = 0 $$

$$ R(n) = \frac{1+R(n)}{3} + \frac{1+R(n-1)}{3} + \frac{2+2*R(n-1)}{3} $$

, which, after some algebra, comes out to:

$$ R(1) = 0 $$

$$ R(n) = \frac 32 * R(n-1) + 2 $$

, where $ n>0 $.

I have a couple of questions about the set-up of this problem.

1. Why is 1 added to the numerators of the first two rational numbers?
2. Similarly, why is 2 added to the numerator of the last rational number?

Finally,

3)

C(n) = the exact number of returns from line 5.1 of RANDOM(n), recursive or not. $$ C(1) = 0 $$

$$ C(n) = \frac {C(n)}{3} + \frac {C(n-1)}{3} + \frac {1+2*C(n-1)}{3} $$

, which, after some algebra, comes out to be:

$$ C(1) = 0 $$

$$ C(n) = \frac 32 * C(n-1) + \frac 12 $$

, where $n>0$.

My main question for this answer is: why is 1 added to the last rational number in the expression? What does that 1 represent?

I am so lost, and desperate. Any attempt to shine light on these answers would be such a great help to me. Thank you.

Answer 1

Firstly, there is one minor typo in the question. The "$T(n) =\frac 32 * T(n-1) + 1$" should be "$T(n) =\frac 32 * (T(n-1) + 1)$" since this equality is said to be obtained by simple algebra from the equality above it. However, this typo does not affect either the question or this answer.

---

The answer to all of your questions are so simple that I can hardly imagine that you missed it. Well, on the other hand, it is indeed very easy to miss it.

Let me give you a simple example to illustrate the answer. Suppose we have the following function, which computes the factorial.

function FACTORIAL(n)
    if n = 1 then
        return 1
    else
        return  n * FACTORIAL(n-1)
    end-if

Suppose we have made a call, FACTORIAL(4). That means we must have called FACTORIAL(3), FACTORIAL(2) and finally FACTORIAL(1). So we have made four calls to this function in total, the last three of which are called recursively. In fact, we have the following recurrence relations for $U(n)$, the number of recursive calls made in FACTORIAL(n). $$U(1) = 0$$ $$U(n) = 1 + U(n-1), \text { for } n\gt 1$$ Notice the first "1" in the last equality, which stands for the call to FACTORIAL with parameter $n-1$ in the code, n * FACTORIAL(n-1) while $U(n-1)$ comes from the number of recursive calls made by FACTORIAL(n-1). In other words, the recursive calls made by FACTORIAL(n-1) does not include that call itself, which is, though of course, counted towards the recursive calls made by FACTORIAL(n). We can also check by contradiction. Let us suppose we did not have that "1". Then we would get $U(4)=U(3)=U(2)=U(1)=0$, which said that we had made no recursive calls to FACTORIAL when we had computed FACTORIAL(4), which is not true at all.

In the same way as in this simple example, all those constant 1's and one 2 in the question come from right where the calls are made. For example, when x = 2, the function will return (3*RANDOM(n-1) + RANDOM(n-1) + 1), which incurs $(1+R(n-1)) + (1+ R(n-1)) = 2 + 2*R(n-1)$ recursive calls.