How to find the average case complexity of Stable marriage problem(Gale Shapley)?

Question

Stable marriage problem

So I know that the worst case complexity will be of the order O(n^2) and the best case is of the order O(n). But how can I calculate the average case complexity

Answer 1

Average case efficiency: $$\mathcal{O} \left( n \log n \right)$$