# Trouble finding average case of a find max algorithm

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.

• 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. Commented Jan 19, 2021 at 9:17

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

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.

• 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.
– Hex
Commented Jan 19, 2021 at 16:17
• Give me some time and I'll write addition about it. Commented Jan 19, 2021 at 17:00
• Did as promised. Write if/when have any questions. Commented Jan 20, 2021 at 1:32
– Hex
Commented Jan 20, 2021 at 3:23
• 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)$)?
– Hex
Commented Jan 20, 2021 at 3:28

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

• Thanks! That was really helpful.
– Hex
Commented Jan 19, 2021 at 16:17
• @Hex Don't forget to upvote the answers you found useful and accept one if it answers your question :) Commented Jan 19, 2021 at 18:30
• 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!
– Hex
Commented Jan 20, 2021 at 3:25