Stable matching problem

Self-enforcing recruitment/matching process

Outcome is stable if E prefers ever one of its accepted applicants to A; or

A prefers her current situation over working for employer E.

Important to think about how resource requirements – the amount of time and space an algorithm will use- will scale with increasing input size

Algorithms should be fundamentally discrete.

An algorithm is efficient if, when implemented, it runs quickly on real input instances

→

Leaves out test case size, and bad algorithms can pass this test and so can good algorithms coded poorly

An algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute-force search.

-too vague

→

An algorithm is efficient if it has a polynomial running time

Helps to see that there might not be an efficient algorithm for a particular problem

O() expressed upper bound, not the exact growth rate

Upper, Lower, and limit bounds

Transitivity, A upper bound = b upper bound, b upper bound = c upper bound, then c upper bound = a upper bound

Polynomials - asymptotic rate of growth is determined by their “high-order term”

Logarithms- slow growing

Exponentials- fast growing

Every exponential grows faster than every polynomial