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:
Give the recurrence equation for the expected running time of RANDOM.
Give the exact recurrence equation for the expected number of recursive calls expected by a call to RANDOM(n).
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.
- Why is 1 added to the numerators of the first two rational numbers?
- 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.