Answer the following questions in regards to the provided pseudocode below. a.)

Question

Answer the following questions in regards to the provided pseudocode below.

a.) Give the recurrence for the expected running time of RANDOM.

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

c.) Give the exact recurrence equation for the expected number of times the rerun statements on line 14 is executed, in all called to RANDOM(n), recursive or not.

Pseudocode:

Function RANDOM(u)

1.   if u = 1 then

2.       return(1)

3.   else

4.       assign x=0 with probability 1/2, or

5.       assign x=1 with probability 1/3, or

6.       assign x=2 with probability 1/6

7.       if x=0 then

8.           return(RANDOM(u-1) + RANDOM(u-2))

9.       end-if

10.       if x=1 then

11.           return(RANDOM(u) + 2*RANDOM(u-1))

12.       end-if

13.       if x=2 then

14.           return(3*RANDOM(u) + RANDOM(u) + 3)

15.       end-if

16.   end-if

end-RANDOM

Explanation / Answer

Sorry,

The Time complexity of the algorithm you have posted is INFINITY

because you have recursively called the function RANDOUM(u) is infinite there is no decrement so it will call the same function without any stop condition

if the value of x =0 then the order of time complexity will be T(n) = T(n-1)+T(n-2) simplied as O(2^n)

a)expected running time if the value of x=0 will be O(2^n) or infinite

b)expected number of recursions if the value of x=0 for every time then number of recursions will be 2^n or infinite

c)it is recursive ,but the number of recursions will be infinite

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.