Average-case Analysis vs Amortized Analysis

출처: http://stackoverflow.com/questions/7333376/difference-between-average-case-and-amortized-analysis

I am reading an article on amortized analysis of algorithms. Following is text snippet.

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 probablistic 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 probablity distribution of algorithm inputs.

An average case bound doesnot preclude the possiblity that one will get "unlucky" and encounter an input that requires most than expected time even if the assumptions on probablity distriubution of inputs are valid.

My questions on above text snippet are

1. In first paragraph how average case analysis relies on probabilistic assumptions about data structures and operations? I know average case analysis depend on probablity of input, but what does above statement mean?

2. What does author mean in second pargarph that average case doesnot valid even if input distrubution is valid?

---

Average case analysis makes assumptions about the input that may not be met in certain cases. Therefore, if your input is not random, in the worst case the actual performace of an algorithm may be much slower than the average case.

Amortized analysis makes no such assumptions, but it considers the total performance of a sequence of operations instead of just one operation.

Dynamic array insertion provides a simple example of amortized analysis. One algorithm is to allocate a fixed size array, and as new elements are inserted, allocate a fixed size array of double the old length when necessary. In the worst case a insertion can require time proportional to the length of the entire list, so in the worst case insertion is an O(n) operation. However, you can guarantee that such a worst case is infrequent, so insertion is an O(1) operation using amortized analysis. Amortized analysis holds no matter what the input is.