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

Question

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

score -1 · Answer 1 · edited May 14 '19 at 20:33

-1

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

edited May 14 '19 at 20:33

dantopa

10,342

answered May 14 '19 at 18:26

Pavi

1

1

Could you elaborte further? – For the love of maths May 14 '19 at 18:31
Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, please use MathJax. – dantopa May 14 '19 at 20:32

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

1 Answers1