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

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

• What do you mean "average case of comparisons"? Do you mean the average quantity of comparisons? That can't possibly be less than $n-1$, so $\log n$ is wrong. Perhaps you should edit the question to clarify? – Wildcard Mar 27 '18 at 1:46
• Of course your analysis assumes the array is in random order. Many times arrays are not in random order. Like sorted arrays. – gnasher729 Mar 29 at 19:59

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

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

• In my case, I'm interested on your second explanation (for $Z_i$). Really liked your explanation, but @LionsWrath explanation tackled my question right on the spot! Tough, thank you for your explanation :) – woz Mar 27 '18 at 11:09