algorithm that determine whether there exists a duplicate integer with expected runtime $O(n)$ Consider an input of unsorted array; we want to determine whether exists a duplicate integer; the algorithm should have expected runtime $O(n)$. 
Note: We want to analysis the expected runtime by counting the number of comparisons in the algorithm.
I know that the brute force requires $\Theta(n^2)$ complexity and the best case is $\Theta(1)$. 
However, for expected runtime analysis; is this equivalent to average case ? Where we consider all possible of runtime complexity and taking expectation over them?
Since the algorithm will be based on the number of comparisons we make. 
the all possible number of comparisons we will make would be a set 
$\{1,2,3,4,...,n-1,n,n+1,...,2n-3, ......\}$ (where $1,..,n-1$, are number of comparisons might be made when compare $A[0]$ to others, and so on; and $n$ is size of array); then taking expectation, but how do I decide the probability of each number of comparisons? For example, if the algorithm terminates with only one comparison, then $A[0] == A[1]$, but I don't how do I determine this probability ?
 A: Assuming that each of the input numbers are represented as a particular string of symbols from a finite alphabet, you can build a trie representing the numbers you have seen so far, while reading them. That will automatically detect duplicates for you, while doing a constant amount of work per input symbol.
A: The algorithm depends very much on the nature of the input.
If the input consists of $n$ integers of some bounded size, then we can consider each integer as a single symbol from a possibly quite large, but finite alphabet. Let there be $k$ symbols in the alphabet; then $k$ is a fixed constant for any input, and any input of length $>k$ contains a duplicate by the pigeonhole principle.
For example, if the input is an array of any length containing $32$-bit integers, then $k=2^{32}.$
The algorithm for this kind of problem begins by counting up to $k+1$ integers in the input. If the count reaches $k+1,$ the algorithm returns "a duplicate exists"; otherwise it performs up to $k(k-1)$ comparisons (the brute force method). So in the worst case we have $k+1$ steps of counting and $k(k-1)$ comparisons; but since $k$ is a fixed constant, the running time of the algorithm is bounded, and the entire algorithm runs in worst-case $O(1)$ time. (The time constant for that $O(1)$ time may be quite large, however.)
A more interesting kind of input allows the integers of input to be strings of digits of any length. Now we have to say what it means to have an input of size $n$; a reasonable interpretation is that $n$ is the sum of the lengths of all the strings (or the sum of the lengths plus the number of strings, to allow for demarcation of the strings). Then Henning Makholm's solution (using a trie) runs in $O(n)$ worst-case time, which implies it has $O(n)$ expected time. 
Another possible interpretation is that we allow the integers to be strings of arbitrary length, but we assume there is some probability distribution that governs the value of each integer. That is, if $m$ is a given integer, then there is some probability $P(m)$ that the next input integer will equal $m.$ 
In that interpretation there is some fixed probability $P_0$ that two integers selected at random from the input will be the same. The expected length of an integer (a bound on the expected time required to compare two integers) is also a fixed value. 
If the first pass of the algorithm merely compares the first and second integers of input, then the third and fourth, then fifth and sixth, etc., then as the length of input goes toward infinity the chance of finding a match approaches $1$ and the expected number of comparisons before finding the match (when there is one) approaches a constant. 
The expected number of comparisons when we compare all possible pairs of input integers (up to the first matching pair) is a little more complicated to deal with, since the pairs are not all independently distributed, but maybe one can show that it's also bounded as $n$ goes to infinity; if so, the expected running time of the entire algorithm is $O(1).$
A: Hash table search and insert are usually both considered $O(1)$ in the average. So if you start with an empty hash table, go through all the elements search and insert at the same time, you find the element in the average at index $k=(n+1)/2$ assuming there is only one duplicate, so you need $O(n)$ hash computations and equality comparisons (inside the hash table) or less.
If you dont use a hash table, but an ordinary list, checking for the collision is $O(m)$ where m is the length of the ordinary list, assuming we dont detect a collision. Taking again the average under the same distribution as before we get $1/6\,n\,(n + 2)$. So you would then need $O(n^2)$ equality comparisons (inside the ordinary list) or less. 
The different program codes look very similar (in Java):
Hash table:
HashSet res = new HashSet();
for (int i=0; i<A.size(); i++) {
    if (res.contains(A.get(i))     /* O(1) */
      return true;
    res.add(A.get(i));             /* O(1) */
}
return false;

Ordinary list:
ArrayList res = new ArrayList();
for (int i=0; i<A.size(); i++) {
    if (res.contains(A.get(i))     /* O(m) */
      return true;
    res.add(A.get(i));             /* O(1) */
}
return false;

We can now make the probability model I was using more explicit. I am using a random variable $X$, for the number of iterations of the outer for loop. The variable is in the range $\{0, .., n\}$, $0$ means a duplicate was found in the first iteration and true was return. $n$ means no duplicate was found and false was return.
I did work with $P[X=i] = 1/(n+1)$ an uniform distribution. The effort of the programm can be viewed as the expected value $E[Y]$ of another random variable $Y = f(X)$, that computes the effort for performing the loop X times. For the hash table we have $Y = X$, and for the ordinary list we have $Y = 1/2\,X\,(X+1)$, neglecting the add() and only considering the contains().
Hash table:
$$E[Y]=E[X]=\sum_{i=0}^n P[X=i] i=\frac{1}{n+1} \frac{1}{2} n (n+1)=\frac{1}{2} n$$
Ordinary list:
$$E[Y]=E[\frac{1}{2} X (X+1)]=\sum_{i=0}^n P[X=i] \frac{1}{2} i (i+1)=\frac{1}{n+1} \frac{1}{6} n (n + 1) (n + 2) = \frac{1}{6} n (n+2)$$
The distribution that was chosen can be viewed as an upper bound, distributions that are more realistic or that also consider that there are multiple duplicates, would give a higher weight to lower values of $X$, which also means a higher weight to lower values of $Y = f(X)$, and thus in the end a lower value of $E[Y]$.
