algorithmtime-complexityprobabilistic-programmingrandomized-algorithm

Probabilistic algorithm, can a best case instance depend on the randomized parameter?

Given this probabilistic algorithm (pseudo code):

p = random(1,n) // 1/n chance for each value ranging from 1 to n
if array[0] = p
{
loop that executes in tetha(n)
}
return 0;

EDIT : possible values in the array are 1..n

I would think that there is a best case instance (array[0] = p) however, this includes a randomized parameter and I have a feeling that it's not right. Am I wrong or right, and why?

Solution

  • For the best-case analysis, you should not consider the probabilistic factors and the only required thing is there is only one case that can be happened (with a positive probability). Hence, the best case analysis is array[0] != p. Then, the time complexity is Theta(1).

    It's the same as the worst case analysis. Suppose p is given (not important it's randomly chosen or not). The worst case time complexity is O(n).

    However, as explcitlt there is a random factor in the algorithm, a rational choice here is average time complexity, which is (n-1)/n + 1/n * Theta(n) = Theta(1). Because, the condition of the if will be satisfied with the probability 1/n and others is (n-1)/n.