You have the task of heating up n buns in a pan. A bun has two sides and cach side has to be heated up separately in the pan. The pan is small and can hold only (at most) two buns at a time. Heating one side of a bun takes 1 minute, regardless of whether you heat up one or two buns at the same time. The goal is to heat up both sides of all n buns in the minimum amount of time. Suppose you use the following recursive algorithm for heating up (both sides) of all n buns. If n=1, then heat up the bun on both sides; if n = 2, then heat the two buns together on each side; if n > 2, then heat up any two buns together on each side and recursively apply the algorithm to the remaining n - 2 buns. a) Set up a recurrence for the amount of time needed by the above algorithm. Solve the recurrence.
b) Show that the above algorithm does not solve the problem in the minimum amount of time for all n >0.
c) Give a correct recursive algorithm that solves the problem in the minimum amount of time.
d) Prove the correctness of your algorithm (use induction) and also find the time taken by the algorithm.