概率算法，最佳案例实例是否取决于随机参数？

Question

给定这个概率算法（伪代码）：

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;

编辑：数组中的可能值为 1..n

我认为存在一个最佳案例实例 (array[0] = p)，但是，这包括一个随机参数，我觉得这是不对的。我是对还是错，为什么？

Answer 1

best-case分析，不需要考虑概率因素，只需要有一种情况可以发生（概率为正）。因此，最好的案例分析是array[0] != p。那么，时间复杂度就是Theta(1).

同最坏情况分析。假设给出 p（随机选择与否并不重要）。最坏情况的时间复杂度是O(n).

但是，由于算法中存在随机因素，这里合理的选择是平均时间复杂度，即(n-1)/n + 1/n * Theta(n) = Theta(1)。因为，if的条件满足的概率是1/n，其他的是(n-1)/n.

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