2
$\begingroup$

I'm trying to find the average case number of times that max is assigned by the algorithm findMax included below.

findMax(list):
    maxNum = -oo  # negative infinity
    for k = 0 to len(list)-1:
        if list[k] > maxNum:
            maxNum= list[k]
    return maxNum
  • The distribution I have considered is uniformly random.

At the back of the textbook I am currently using, the solution is said to be $O(logn)$, however, using the approach that I have came up with (which I'm not quite sure why is incorrect), I got $O(n)$ instead.

In my approach: I have used the following formula $$E[t_n] = \sum^{n}_{t=1}t \cdot Pr(t_n=t)$$ And, I considered how many times maxNum was updated to calculate the expected value. First, I noticed that if the max would have been the first element, maxNum would have only been updated once. If the max was the second element, then it would have been updated twice, and so forth. Using this reasoning, I deduced that the probability of maxNum appearing in the nth position is $\frac{1}{n}$. Then, I got $$E[t_n] = 1 \cdot Pr(t_n = 1) + 2 \cdot Pr(t_n = 2) + ... + n \cdot Pr(t_n = n)$$ $$=\frac{n+1}{2}$$ $$\Rightarrow O(n)$$.

I am a bit lost and am unsure where my mistake took place exactly.

$\endgroup$
1
  • 1
    $\begingroup$ If the maximum element is the n'th, then maxNum is not necessarily updated n times. Consider for exemple the case where the second largest element is in first position. Then maxNum is updated twice no matter where the largest element is. $\endgroup$ – Tassle Jan 19 at 9:17
2
$\begingroup$

Let me start with your main question "where my mistake took place exactly?" - in short, the whole point is in the wrong choice of the probability distribution for $Pr(t_n=t)$. You are considering the number of changes in the maximum, i.e. how many times maxNum was updated, but you are using probabilities for the location the maximum in the array.

Before starting analysis, let me say, that, for example, CLRS Introduction to Algorithms, Third Edition, on page 120, calls formula you are using "cumbersome" for calculating and choose indicator function way. Donald Ervin Knuth in TAOCP Volume 1, Third Edition, 1997, pages 96-101 are using generating functions mechanism.

Now in more detail: for simplicity, let's consider the case when you have only 4 elements in the array and let us consider only such 4s in which all elements are different i.e. $(a, b, c, d)$, where all are different. I bring the pseudocode for this case from the book Jeffrey J. McConnell, Analysis of Algorithms: an Active Learning Approach , 2001, page 3

maxNum = a
if b > maxNum then
    maxNum = b
end if
if c > maxNum then
    maxNum = c
end if
if d > maxNum then
    maxNum = d
end if
return maxNum

where your loop is simply decomposed into separate lines and in 1-st line is not used negative infinity. As we are considering function $T$ the number of maxNum updatings, i.e. number of assignements, then, obviously $T$ have values 1,2,3,4. Probability distribution for $T$ can be counted directly and is

$Pr(T=1)$: $\frac{1}{4}=\frac{4}{16}$

$Pr(T=2)$: $\frac{1}{4}+\frac{1}{4}\cdot \frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{7}{16}$

$Pr(T=3)$: $\frac{1}{4}\cdot \frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{4}{16}$

$Pr(T=4)$: $\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{1}{16}$

Anticipating the question of how these calculations were obtained, let me say that it is enough to simply consider the possible options for finding the maximum in the all fours and count their fractions.

To calculate general case, where we have $n$ elements in array it's more easy to find reccurence relation for $T(n)$: $$T(n) = n \cdot T(n-1) + (n-1)!$$ and from here obtain expected value

$$\frac{ T(n)}{n!} = \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ... + \frac{1}{n-1} + \frac{1}{n} = \sum_{i=1}^{n}\frac{1}{i} - 1 =\\ = \ln n + \gamma + \varepsilon_{n} -1 = \ln n +O(1)$$

where $\gamma$ is Euler–Mascheroni constant and $\varepsilon_{n} \sim \frac{1}{2n}, n\rightarrow \infty$.

Addition.

Now more about calculating probabilities in case of 4s $(a, b, c, d)$ where all are different:

The proportion of such fours in which the maximum is in the first place, i.e. maximum is $a$, is equal to the proportion of such fours in which the maximum is in second place , i.e. maximum is $b$, and is $\frac{1}{4}$. Same for cases with $c$ and $d$.

Such fours where maximum is $a$ and only they gives $1$ assignement for maxNum, i.e. $T=1$, and so we obtain $Pr(T=1)$: $\frac{1}{4}=\frac{4}{16}$.

Such fours where maximum is $b$ gives $2$ assignements, $T=2$, but we can obtain $2$ assignements also from cases where $c$ or $d$ is maximum, so we can say, that $Pr(T=2)$ includes $\frac{1}{4}$ plus some more numbers i.e. we obtain first summand for $Pr(T=2)$.

Now let's take fours where maximum is $c$. This case can produce values $2, 3$ for $T$: when $b \gt a$, then $T=3$ and when $b \lt a$, then $T=2$. As proportion for both is $\frac{1}{4}\cdot \frac{1}{2}$, then we obtain second summand for $Pr(T=2)$ and first summand for $Pr(T=3)$.

Last we consider 4s where maximum is $d$. Hope it's easy to understand, that here we have $4$ parts with equal proportion $\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}$: 1) $b \gt a, c \gt b$ which gives $T=4$, 2) $b \gt a, c \lt b$ and $b \lt a, c \gt a$ which gives $T=3$, 3)$b \lt a, c \lt a $ which gives $T=2$. Correspondingly we obtain all remained summands.

At end let me say, that it's easy to write code for some virtual experiment, for example on python from random import uniform, I can share if needed, and check, that practical frequences approximates theoretical probabilities.

$\endgroup$
7
  • $\begingroup$ Thanks for your response! Would you mind expanding a little bit on how you got $Pr(T=1) = \frac{1}{4}$, $Pr(T=2) = \frac{1}{4} + \frac{1}{4} \cdot \frac{1}{2} + \frac{1}{4} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{7}{16}$ and so on. I am just unsure about this part and it seems to be the most crucial part here, so a brief explanation would be greatly appreciated. $\endgroup$ – Hex Jan 19 at 16:17
  • $\begingroup$ Give me some time and I'll write addition about it. $\endgroup$ – zkutch Jan 19 at 17:00
  • $\begingroup$ Did as promised. Write if/when have any questions. $\endgroup$ – zkutch Jan 20 at 1:32
  • $\begingroup$ That made perfect sense, thanks a lot for your help!! $\endgroup$ – Hex Jan 20 at 3:23
  • $\begingroup$ Would you say that a good way of tackling such questions is first and foremost coming up with small cases, such as the one you have come up with (i.e., the case where $(a,b,c,d)$)? $\endgroup$ – Hex Jan 20 at 3:28
2
$\begingroup$

If the maximum element is the $n$'th, then $\text{maxNum}$ is not necessarily updated n times. Consider for example the case where the second largest element is in first position. Then $\text{maxNum}$ is updated twice no matter where the largest element is.

Let $U_n$ be the average number of updates of $\text{maxNum}$ for a list of size $n$. Let $i_\max$ denote the index of the maximum element (or to be precise the random variable corresponding to that value). Notice that no update is done once $i_\max$ is reached. Thus, conditioned on the fact that $i_\max = i$, the average number of updates of $\text{maxNum}$ is $U_{i-1}+1$ (where we define $U_0=0$).

Using the law of total probability, we get $$U_n = \sum_{i=1}^{n} (U_{i-1}+1) \cdot P(i_\max = i) = \sum_{i=0}^{n} (U_{i-1}+1)/n.$$ (I start indexing at 1 like you did)

Multiplying this by $n$ we get $$n\cdot U_n = \sum_{i=0}^{n} (U_{i-1}+1).$$

Similarly, we have $$(n-1)\cdot U_{n-1} = \sum_{i=0}^{n-1} (U_{i-1}+1).$$

Subtracting the second from the first gives $$ n\cdot U_n - (n-1)\cdot U_{n-1} = U_{n-1}+1$$.

Rearranging: $$U_n = U_{n-1} + \frac{1}{n}$$.

Expanding you get $U_n = 1+\frac{1}{2}+\frac{1}{3}+\ldots \frac{1}{n}$. Thus $U_n$ is the $n$'th harmonic sum $H_n$. In fine, $U_n = H_n \in O(\log(n))$.

$\endgroup$
3
  • $\begingroup$ Thanks! That was really helpful. $\endgroup$ – Hex Jan 19 at 16:17
  • $\begingroup$ @Hex Don't forget to upvote the answers you found useful and accept one if it answers your question :) $\endgroup$ – Tassle Jan 19 at 18:30
  • $\begingroup$ I wish I could accept two answers instead of one since your solution also offered me a different way of thinking about this problem and helped immensely. I will be sure to upvote this solution when I will get 15 reputation points since I can't as of now. In any case, I appreciate your response. Thanks for your help! $\endgroup$ – Hex Jan 20 at 3:25

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.