structural:summarization, information:filtering, structural:scholar_edition, linguistic:translation
Implementation details and time analysis

To implement the algorithm efficiently, each employer needs to be able to find its next applicant quickly, and each applicant needs to be able to compare employers quickly. One way to do this is to number each applicant and each employer from 1 to n {\displaystyle n}, where n {\displaystyle n} is the number of employers and applicants, and to store the following data structures:

Setting up these data structures takes O (n 2) {\displaystyle O(n^{2})} time. With these structures it is possible to find an employer with an unfilled position, make an offer from that employer to their next applicant, determine whether the offer is accepted, and update all of the data structures to reflect the results of these steps, in constant time per offer. Once the algorithm terminates, the resulting matching can be read off from the array of employers for each applicant. There can be O (n 2) {\displaystyle O(n^{2})} offers before each employer runs out of offers to make, so the total time is O (n 2) {\displaystyle O(n^{2})}.

Although this time bound is quadratic in the number of participants, it may be considered as linear time when measured in terms of the size of the input, two matrices of preferences of size O (n 2) {\displaystyle O(n^{2})}.