title: what is expected number of writes while finding maximum in an array?
body: <p>I have a random access list of positive integers with length N, and I have a variable MAX and I know that the maximum number in my list is M(may not have M in the array but cannot have more than M in it). The algorithm is I have random access to my list, in each access I write the value exist in variable MAX, if and only if it contains a value more than MAX.</p>
  
  <p>Now I am wondering how I can compute the <strong>expected number of writes to variable MAX</strong> with this algorithm?</p>
  
  <p>Hope this example makes it more clear:</p>
  
  <pre><code>List: 2 - 5 - 3 - 1 - 9
  Read 2 =&gt; Max = 2 (1 write)
  Read 5 =&gt; Max = 5 (2 writes)
  Read 3 =&gt; Max = 5 (2 writes) (do not write)
  Read 1 =&gt; Max = 5 (2 writes) (do not write)
  Read 9 =&gt; Max = 9 (3 writes) 
  </code></pre>