For each problem below, do not write pseudocode. Explain with words why your algorithm is correct and analyse its running time. Problem 1 (rating restaurants) You are writing a blog about restaurants in various cities. You have a list of the 16 top restaurants in La Habana but you don't trust the reviewer. You have a friend in there who is willing to help and all you want to do is provide the best of these 16 restaurants and the worst of these 16 restaurants. So you ask your friend to compare restaurants and give you her opinion on the best and the worst. (a) Briefly explain how your friend can help you doing 30 comparisons.
(b) Design an algorithm your friend can apply to help you if the list has n 2k many restaurants.
Your input is a list of n restaurants and your friend can compare any two in O(1) time. You want to output the best and the worst. Explain why your algorithm is correct and state and analyse its running time. Fastest (and correct) solutions worth more credit.