3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Wildcard Mar 27 '18 at 1:46
  • $\begingroup$ Of course your analysis assumes the array is in random order. Many times arrays are not in random order. Like sorted arrays. $\endgroup$ – gnasher729 Mar 29 at 19:59
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 :) $\endgroup$ – woz Mar 27 '18 at 11:09

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.