2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ thanks so much, this is very helpful; so every time when I'm dealing with expected runtime; I consider the sample space as the set of all possible input. Based on the input, I calculate the runtime for each one; then there will be a distribution over all possible inputs; finally, I use expectation function; is there anymore similar type of questions that can get me to practice ? $\endgroup$ – ElleryL Aug 13 '17 at 5:43
  • $\begingroup$ Your description is accurate. I recommend checking out the average time analysis of Quicksort. $\endgroup$ – Yuval Filmus Aug 13 '17 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.