5. We proved in class that during the TMA, at most O(n) rejections might occur. In this question you are requested to show a matching lower bound in the worst case) and also that a much faster execution could occur, if the input is 'friendly enough'. (a) Describe an input of preferences lists n females and n males, which will cause the total number of rejections, ("no I will never marry you) occurring during the algorithm to be as small as possible. What is this number (as a function of n) ? Prove your answer. (b) Repeat the previous bullet, but now the number of rejections should be as large as possible. running time of TMA is as large as possible (for a set of n people, when n is given to you). Same, but now as what is the input that yields the minimum time. 5. We proved in class that during the TMA, at most O(n) rejections might occur. In this question you are requested to show a matching lower bound in the worst case) and also that a much faster execution could occur, if the input is 'friendly enough'. (a) Describe an input of preferences lists n females and n males, which will cause the total number of rejections, ("no I will never marry you) occurring during the algorithm to be as small as possible. What is this number (as a function of n) ? Prove your answer. (b) Repeat the previous bullet, but now the number of rejections should be as large as possible. running time of TMA is as large as possible (for a set of n people, when n is given to you). Same, but now as what is the input that yields the minimum time