Problem 2. The Australian Government Department of Health maintains a list of n people who have been double vaccinated against Covid, called list_double. At the end of 2022, an aggregated list of m people who have been vaccinated the third time in 2022 with booster shots is created, called list_triple. Note that m ≤ n. People in each list are identified by their unique ID numbers (e.g., passport numbers) and are entered into the lists in chronological order. It is required to design an algorithm that takes as input the two lists and returns a new list of people who are double vaccinated but haven’t received their third shots. A reminder will be sent to all people in this list to take their booster shots. 

a) Design (describe + complexity analysis) a brute-force algorithm that performs the aforementioned task. Analyse the time complexity of the algorithm using the big-O notation. Pseudocode is NOT required.

b) Design (describe + complexity analysis) a transform-and-conquer algorithm with time complexity O(nlogm) that performs the aforementioned task using at most a constant amount of extra space (apart from the input/output).

c) Design (describe + pseudocode + complexity analysis) an algorithm with (average-case) time complexity O(n) that performs the aforementioned task. There is NO restriction on the space complexity.