a. Solve the following recurrences using the Master Theorem. State the case and the constant values used:

Use the change of variable

Show your work

b. Let be a max-heap with and consider the index i such that . Assume that all the elements of A are distinct. Write the pseudocode of an algorithm which replaces by and then re-arranges the elements of A into a max-heap. The running time of your algorithm must be .