Is this a correct approch of finding expected runtime of an algorithm?
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] &gt; 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] &gt; 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] &gt; 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$.