Finding the average time complexity for a max algorithm

Question

I'm trying to find the average-case number of times that max is assigned a value by the below algorithm find_max.

find_max(L):
 max = -oo # negative infinity
 for k = 0 to len(L)-1:
 if L[k] > max:
 max = L[k]
 return max

However, I'm struggling to come to a solution. So far, this is what I have done:

I'm defining the sample space to be L containing values which are between 1 and 100, and having them uniformly distributed.

The worst-case running time is $T(n) = n + 1$ because of the initial max assignment, and the case where every element is larger than the previous one.

The best-case running time is $T(n) = 2$ which is the case where all elements have the same value, so there is the initial max assignment and one assignment in the for loop.

So, the running time is distributed between 2 and n+1 inclusive.

Then, the average-case running time is:

$E[t_{n}] = \sum_{2}^{n+1} t \cdot P(t)$

However, I am having difficulty defining the Random Variable T and the probability formula for values of T.

Answer 1

Let $\small n = \mathsf{len}(L)$ and $\small t_n$ be the times that $\small \mathsf{max}$ is assigned a value. For $\small 0 \leq i < n,ドル define a random variable $\small X_i$ as $$ \small X_i = \begin{cases} 1 & \text{if } L[i] > \text{$\mathsf{max}$ in the $i$-th iteration of the algorithm}\\ 0 & \text{otherwise} \end{cases} $$ Then we have $$ \small t_n = 1 + \sum_{i=0}^{n-1} X_i $$ By linearity of expectation, $$ \small \mathbb{E}[t_n] = 1 + \sum_{i=0}^{n-1}\mathbb{E}[X_i] $$ Observe that $\small X_i = 1$ if and only if $\small L[i] > \max\{L[0], L[1], \cdots, L[i-1]\}$. Therefore \begin{align} \small \mathbb{E}[X_i] = \Pr[X_i = 1] =&\small \sum_{v=1}^{100} \Pr[L[0] < v, L[1] < v, \cdots, L[i-1] < v, L[i] = v] \\ \small= &\small \sum_{v=1}^{100} \left(\frac{v-1}{100}\right)^i \cdot \frac{1}{100} \end{align} We thus conclude \begin{align} \small \mathbb{E}[t_n] =&\ \small 1 + \sum_{i=0}^{n-1}\sum_{v=1}^{100} \left(\frac{v-1}{100}\right)^i \cdot\frac{1}{100} \\ \small =&\ \small 1 + \frac{1}{100}\sum_{v=1}^{100}\sum_{i=0}^{n-1}\left(\frac{v-1}{100}\right)^i \\ \small =&\ \small 1 + \frac{1}{100}\sum_{v=1}^{100}\frac{1 - \left(\frac{v-1}{100}\right)^n}{1 - \frac{v-1}{100}} \\ \small\text{(for sufficiently large $n$)}\quad\quad\approx&\ \small1 + \frac{1}{100}\sum_{v=1}^{100} \frac{1}{1 - \frac{v-1}{100}} \\ \small = &\ \small 1 + \sum_{v=1}^{100}\frac{1}{101-v} \\ \small =&\ \small 1 + H_{100} \end{align} where $\small H_{100}$ is the $\small 100$-th harmonic number.