Hello, I would like to get help with the following algorithm, thank you in advance.

For the problem, provide the following: 1) A description of your algorithm in pseudo-code (well written sentences/steps are fine), 2) Proof of correctness, and 3) analysis of run time.

3. Good Goblins are Easy to Find: At Hogwarts a new shipment of n goblins has arrived. To be of any use, a goblin must be completely truthful (never lies). Unfortunately, not all of the n goblins in the shipment are truth tellers. Only some are truth-tellers, and some are deceivers. It is your task to design an algorithm to separate the truth-teller goblins from the deceiver goblins. To do this, you have one tool available: You may combine any two goblins and have them state whether the other goblin is a truth-teller or a deceiver. A truth-teller will always say correctly what the other goblin is, but a deceiver may lie (but also may sometimes tell the truth to REALLY confuse you). For any two goblins that you test, the following can be concluded from the goblin responses: Goblin A says Goblin B says Conclusion B is a truth-teller A is a truth-teller both are truth-tellers or both are deceivers B is a truth-teller A is a deceiver at least one is a deceiver B is a deceiver A is a truth-teller at least one is a deceiver B is a deceiver A is a deceiver at least one is a deceiver Show that if more than n/2 goblins are deceivers, it is impossible to determine which goblins are the truth-tellers using only the pairwise testing strategy. Consider the problem of identifying 1 truth-teller goblin. Show that if we assume that more than n/2 of the goblins are truth-tellers, then the problem of finding a single truth-teller from n goblins can be reduced to a problem of about half the size using n/2 goblin comparisons. Design an algorithm to identify all the truth-tellers in O(n) goblin comparisons if you start with more than half of the goblins as truth-tellers. Be sure to argue that your algorithm is correct, and analyze the run time. Suggestion: use the above observation to design a recursive solution. Then, use a recurrence equation to analyze the run time of your solution