The Union-Find problem of \textit{A. V. Aho, J. E. Hopcroft} and \textit{J. D. Ullman} [The design and analysis of computer algorithms, Addison-Wesley Publ. Comp. (1974; Zbl 0326.68005)] consists of maintaining a representation of a partion of an \(n\)-set, where the operations are Find and Union. This problem arises in several applications. Also, Hopcroft and Ullman developed two algorithms for the above problem; the Quick-Find (QF) and the Weighted Quick Find (WQF) algorithms. The worst-case analysis of these (and other) algorithms are extensively investigated. About the average-case behavior is much less known. This paper shows that the expected running time of QFW is \(cn+o(n/\log n)\) (where \(c\)=2.0847) proving affirmatively the conjecture of \textit{D. E. Knuth} and \textit{A. Schönhage} [Theor. Comput. Sci. 6, 281-315 (1978; Zbl 0377.68024)]. It is also shown that, concerning QF, the expected cost of \((n-1)\) Union is \(n^ 2/8+O(n(\log n)^ 2)\), and, in general, even QF is reasonable efficient on the average (not performing too many Unions). To settle these problems the paper uses techniques from Random Graph Theory. The derivations are lengthy and quite involved.