1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A very well written question! Here is one part I do not understand, though. "Why does the constant 1 in the original equation not matter to the equation?" which constant in which original equation does not matter to which equation? $\endgroup$ – Apass.Jack Sep 29 '18 at 17:38
  • $\begingroup$ Thank you! I was referring to the 1 at the beginning of the first answer, right before T(n)/3. The final solution to the equation also contains a +1, but if the correct operations were applied to the constant, the +1 would be some rational number. I just wanted to know why the value of the constant does not matter. $\endgroup$ – Nat Porter Sep 29 '18 at 18:58
  • $\begingroup$ Sure, although I'm not sure why the two are typos. Do you mind explaining that in the comments section? Thank you! $\endgroup$ – Nat Porter Sep 30 '18 at 6:19
  • $\begingroup$ Ah, ok, that's actually part of my question. I wanted to know if the 3 had anything to do with the result of the recurrence equation. I'm assuming the issue with the parentheses also has to do with my misunderstanding of the problem. Do you mind explaining my mistake in your answer? Normally, I would correct it, but I haven't made a typo, I actually do not know how to understand the question. $\endgroup$ – Nat Porter Sep 30 '18 at 6:41
  • $\begingroup$ Yes, the 3 didn't matter to the answer, so it makes sense to remove it anyways. Also, yes, the +1 makes sense to move within the parentheses. $\endgroup$ – Nat Porter Sep 30 '18 at 7:08
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.