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