Average Case Analysis for finding max and min value on an array

Question

Given the following algorithm, to find the maximum and minimum values of an array - don't mind the language:

MaxMin(A[1..n])
    max = A[1];
    min = A[1];
    for (i = 2; i<=n; i++)
        if (A[i] > max)
            max = A[i];
        else if (A[i] < min)
            min = A[i];
    print(max, min);

I need to do a probabilistic analysis for the average case of comparisons that will be made on its execution.

So far, my solution is:

Given an indicator random variable: $$ X_i = \begin{cases} \text{1, if max $>$ $A[i]$}\\ \text{0, if max $<$ $A[i]$}\\ \end{cases} $$

and assuming an uniform distribution for $A[1..n]$, the expected probability is: $$E[x] = \sum\limits_{i=1}^{n} Pr(X_i)$$

where $$Pr(X_i)$$ is the probability of the i-th element be the $max$ element in $A[1..n]$. It's possible to determine that: $$Pr(x_1) = 1, Pr(x_2) = 1/2, Pr(x_3) = 1/3 ,..., Pr(x_n) = 1/n$$ and thus for an array of size $n$ the expected value can be calculated as:

$$E[x] = 1 + 1/2 + 1/3 + ... + 1/n = \sum\limits_{i=1}^{n}{\frac{1}{i}} \approx \log{n}$$

And the same goes for $min$, which will give the same result $\log{n}$. (1)

My questions are: is it correct? Does the complexity for the average case of the given algorithm is $\theta(\log{n})$? Can I use the argument pointed by (1), just modifying $X_i$ so: $$ X_i = \begin{cases} \text{1, if min $<$ $A[i]$}\\ \text{0, if min $>$ $A[i]$}\\ \end{cases} $$

I already read this (unfortunately the link to the video isn't available), but it only explains for $max$ and my analysis must be for both $max$ and $min$.

Answer 1

First, note that the first comparison will always compare $n-1$ times, independent of the distribution of the input. So, what you really want to know is how many times the second part of the if compares. For this, you can use a indicator random variable like this:

$$ X_i = \begin{cases} \text{1, if A[i] $\le$ $\max$}\\ \text{0, if A[i] $>$ $\max$}\\ \end{cases} $$

So, just like you did, assuming an uniform distribution for $A[1..n]$, the expected probability is:

$$E[x] = \sum\limits_{i=1}^{n} Pr(X_i)$$

But we do not want $Pr(i=\max)$, we want $\overline{Pr(i=\max)}$, like we stated before. So, using your probability of the $i-th$ element to be the $max$ element:

$$Pr(i = \max) = 1/i$$

We have this complement:

$$\overline{Pr(i=\max)} = (1 - 1/i)$$

From which we can put in the expected probability:

$$E[x] = \sum\limits_{i=2}^{n} (1 - 1/i) = \sum\limits_{i=2}^{n}1 - \sum\limits_{i=2}^{n}1/i = n - 1 - (\ln|n| - 1 + \Theta(1))$$

So, to get the total quantity of comparisons, we can just sum the number of comparisons of the two parts. Note that the $\Theta(1)$ can absorb a constant values.

$$(n - 1) + n - 1 - \ln|n| + 1 + \Theta(1) = 2n - 1 - \ln|n| + \Theta(1)$$

And we get the expected total number of comparions:

$$2n - \ln|n| + \Theta(1)$$

Answer 2

To answer your questions, I need to consider two cases:

(1) You are looking for either min or max. Then,

(1-1) is it correct? Yes, it is correct.

(1-2) Does the complexity for the average case of the given algorithm is $\Theta(logn)$? Indeed it is. My experience in practice is that it does not work that way (or at least the is a large constant involved).

(1-3) Can I use the argument pointed by (1), just modifying $X_i$? Yes, you can do that too.

(2) You are looking for both min and max. Then, the scenario is different. You should have something like: $$ Z_i = \begin{cases} \text{1, if max $>$ $A[i]$ and min $<$ A[i]}\\ \text{0, if max $<$ $A[i]$ and min $>$ A[i]}\\ \end{cases} $$

Then you can calculate $E[Z]$. It is also possible to calculate $E[XY]$, where $X$ is for max, and $Y$ is for min. Try different techniques and see which one works easier.