2
$\begingroup$

I've read some posts about counting the number of assignment inside code of finding the maximum value in array like this:

FindMax(L):
   n = len(L)
   max = L[1]
   for i = 2..n:
      if (max < L[i]) 
          max = L[i] (**)
   return max

According to this post and post, it's about the array that elements are strictly distinguish. So if the array contains values may be duplicated (for example, elements are integer in range [1, m], m = 3, with any length of array), how could we calculate the number of (**) will be executed in average case?

$\endgroup$
  • $\begingroup$ Average case is with respect to an input distribution. Which input distribution do you have in mind? Each element is chosen independently and uniformly at random from $1,\dots,m$, for some constant $m$? $\endgroup$ – Yuval Filmus Jun 9 '18 at 9:56
  • $\begingroup$ Use linearity of expectation and indicator variables. All you need to know is the probability that element $i$ is larger than all previous elements. $\endgroup$ – Yuval Filmus Jun 9 '18 at 9:59
  • $\begingroup$ @YuvalFilmus yes, it is. $\endgroup$ – Le Duong Tuan Anh Jun 9 '18 at 10:16
  • $\begingroup$ @YuvalFilmus So could you please explain it more clearly? $\endgroup$ – Le Duong Tuan Anh Jun 9 '18 at 10:46
1
$\begingroup$

Let us consider the following distribution: each array element is chosen independently and uniformly from $\{1,\ldots,m\}$. Let us denote by $I_i$ the indicator variable for the event that ( ** ) gets executed for the $i$th element (so $I_i = 1$ if ( ** ) gets executed, and $I_i = 0$ otherwise). Linearity of expectation shows that the expected number of times that (**) gets executed is $$ \sum_{i=2}^n \Pr[I_i]. $$ (This uses the fact that $\mathbb{E}[I_i] = \Pr[I_i]$.)

It remains to compute the probability of $I_i$. If $A[i] = j$ then (**) happens iff $A[1],\ldots,A[i-1] \in \{1,\ldots,j-1\}$, which happens with probability $\bigl(\tfrac{j-1}{m}\bigr)^{i-1}$. Therefore $$ \Pr[I_i] = \sum_{j=2}^m \frac{1}{m} \left(\frac{j-1}{m}\right)^{i-1}. $$ In total, we get $$ \sum_{i=2}^n \Pr[I_i] = \sum_{j=2}^m \frac{1}{m} \sum_{i=2}^n \left(\frac{j-1}{m}\right)^{i-1}. $$ You take it from here.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 for this excellent explaination :D btw it is the mean of number of times, so are there any way for me to calculate the variance? $\endgroup$ – Le Duong Tuan Anh Jun 10 '18 at 7:11
  • $\begingroup$ The same approach works for other moments as well, though the calculations are more difficult. You have to calculate the probability of both events $I_i$ and $I_j$ occurring simultaneously. $\endgroup$ – Yuval Filmus Jun 10 '18 at 7:54
  • $\begingroup$ I've got it after a little time of thinking. Btw after some step of calculating, I couldn't get the formula that only depends on n & m. I only could get the following: [1 - (k/m)^(n-1)] / (m - k), for k = 1..m-1. So are there anyway to continue? $\endgroup$ – Le Duong Tuan Anh Jun 10 '18 at 8:35
  • $\begingroup$ Sometimes getting a nice exact expression is too much to ask for, and instead we are interested in sharp asymptotic estimates. $\endgroup$ – Yuval Filmus Jun 10 '18 at 9:00

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.