I'm having trouble fully understanding how to write the recurrence for the expected running time of a randomized algorithm.
I believe I'm doing it correctly, but if someone could look over it, that'd be a huge help.
Here's the pseudocode for the algorithm:
printIntegers(A, n) // an array A of integers is the input, with n integers
if A.length > 0
for i = 1 to A.length
print A[i]
randInt = rand(1, 10)
if randInt != 10
return
else printIntegers(A, n-1)
The only random part is the random generator between 1 and 10. I'm trying to understand how that would translate in the recurrence.
I'm thinking:
T(n) = O(n) if a != 10 probability = 9/10
T(n-1) + O(n) a = 10 = 1/10
T(n-2) + O(n)
....
T(0) + O(n)
This makes sense in my head, and then the expected running time would be O(n). Am I approaching this correctly?
Aucun commentaire:
Enregistrer un commentaire