jeudi 3 mars 2016

Basic randomized algorithm recurrence

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