title: Difference between average case and amortized analysis
body: <p>I am reading an article on amortized analysis of algorithms. The following is a text snippet.</p>
  
  <blockquote>
    <p>Amortized analysis is similar to average-case analysis in that it is
    concerned with the cost averaged over a sequence of operations.
    However, average case analysis relies on probabilistic assumptions
    about the data structures and operations in order to compute an
    expected running time of an algorithm. Its applicability is therefore
    dependent on certain assumptions about the probability distribution of
    algorithm inputs.</p>
    
    <p>An average case bound does not preclude the possibility that one will
    get “unlucky” and encounter an input that requires more-than-expected
    time even if the assumptions for probability distribution of inputs are
    valid.</p>
  </blockquote>
  
  <p>My questions about above text snippet are:</p>
  
  <ol>
  <li><p>In the first paragraph, how does average-case analysis “rely on probabilistic assumptions about data structures and operations?” I know average-case analysis depends on probability of input, but what does the above statement mean?</p></li>
  <li><p>What does the author mean in the second paragraph that average case is not valid even if the input distribution is valid?</p></li>
  </ol>
  
  <p>Thanks!</p>