Stable Matching Running TIme

We know that the Propose-and-reject algorithm terminates in at most n² rounds when there are n students and n colleges.

(a) It seems possible that the algorithm may complete in fewer rounds if the preference lists have a certain structure. Describe a family of preference lists, one for each value of n, such that the propose-and-reject algorithm will complete in only O(n) rounds when run on these preference lists.

More specifically, your solution should do the following: for an arbitrary positive integer n, give a precise description of preference lists for n colleges and n students. Let T(n) be the number of rounds that the propose-and-reject algorithm takes for these preference lists. Prove that T(n) is O(n).

(b) Could it be the case that the running time is actually O(n) for all preference lists? Show that this is not true by designing preference lists so that the number of rounds of the algorithm is (n²).