Is this a correct approch of finding expected runtime of an algorithm?

Question

Consider two algorithms; we analysis their run time only by counting the number of comparisons

TwoMax1(A):   
     S = negative infinite
     L = negative infinite
     loop through the array A
         if A[i] > L:
             S = L
             L = A[i]
         else
            if A[i] > S
                S = A[i]
    return (L,S)



 TwoMax2(A):   
     S = negative infinite
     L = negative infinite
     loop through the array A
         if A[i] > S:
            if A[i] > L:
             S = L
             L = A[i]
            else
                S = A[i]
    return (L,S)

Here is my approach for the first algorithm:

(1) define our sample space. Since the returned output is a pair, maximum and second maximum could be anywhere in the array. For each maximum, there are $(n-1)$ possible index for second maximum, and we have $n$ possible index for the maximum value; So sample space: $S = \{(A[0],A[1]),(A[0], A[2]),(A[0],A[3]),\dots\}$ and so on.

Define an indicator $I_i = 1$ iff $A[i] > \max \{A[0], A[1], \dots, A[i-1]\}$.

The total expected comparison of comparing to maximum would be $$\mathbb{E} (\sum_{i=0}^n I_i) = \sum_{i=0}^n \mathbb{E}(I_i) = \mathrm{Prob}(A[i] > \max \{A[0], A[1],\dots, A[i-1]\}) = \frac{n+1}{2}.$$

where $$\mathrm{Prob}(A[i] > \max \{A[0], A[1], \dots, A[i-1]\}) = \frac{i}{n}$$ because under the sorted array, we have $\frac{i}{n}$ chance of choosing a integer that greater than $A[0], A[1],\dots,A[i-1]$.

Now similar, the total expected comparison of comparing to second maximum would be same; and we sum two parts together up is $n+1$.

Is this a good way of approaching? If so, I also want to know some other ways of doing it, for example, define a different random variable to solve the second function.

Answer 1

First of all, notice that in TwoMax1, $A[i]$ is always compared to $L$. This already gives you $n$ comparisons. If $A[i]$ is not the current maximum, then it is compared to $S$. This happens with probability $1-1/i$ (see below). Therefore the total expected number of comparisons is $$ n + \sum_{i=1}^n \left(1 - \frac{1}{i}\right) = 2n - H_n = 2n - \log n - \gamma + O\left(\frac{1}{n}\right). $$

In TwoMax2, $A[i]$ is always compared to $S$. Again, this gives you $n$ comparisons. If $A[i] > S$, which happens when $A[i]$ is one of the two maximal elements, then $A[i]$ is compared to $L$. When $i = 1$, it is always the case that $A[i] > S$, and otherwise it happens with probability $2/i$. Therefore the expected number of comparisons is $$ n + 1 + \sum_{i=2}^n \frac{2}{n} = n + 2H_n - 1 = n + 2\log n + \gamma - 1 + O\left(\frac{1}{n}\right). $$

The second algorithm thus makes roughly half as many comparisons than the first algorithm.

---

You mention that the sample space consists of all outcomes. But in fact, the sample space consists of all inputs, or in your case, all input permutations. You are analyzing the algorithm with respect to the uniform distribution over this sample space.

Also, the probability that $A[i] > A[1],\ldots,A[i-1]$ (numbering elements from zero) is not $i/n$ (consider for example the case $i=1$!) but rather $1/i$. The reason is that if $A[1],\ldots,A[n]$ is a random permutation then $A[1],\ldots,A[i]$ is a random permutation of $\{A[1],\ldots,A[i]\}$. In particular, $A[i]$ is a random element of $\{A[1],\ldots,A[i]\}$, and so it equals the maximum with probability $1/i$.