Pergunta

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

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top