a) Suppose you draw the decision tree for mergesort when applied to an array of 4 elements. - What will be the exact length of the longest path in the tree? (Assume that the optimization described above is not being used.) - What will be the exact length of the shortest path in the tree? (Assume that the optimization described above is not being used.) - What will be the exact length of the shortest path in the tree? (Assume that the optimizationdescribed above is being used.)

b) Suppose you draw the decision tree for mergesort when applied to an array of 2k elements. What will be the exact length of the longest path in the tree? (Assume that the optimization described above is not being used.) Your answer should be a formula in which k is the only variable. Simplify your formula as much as possible and express it using standard mathematical notation. Use ^ as the exponentiation operator. Your formula cannot contain summations. Write your formula as a sum or difference of terms, with higher order terms appearing before lower order terms. Include no spaces. Indicate multiplication by adjacency, not by using a multiplication symbol. Use parentheses only where your formula would mean something else if you left them out. Here are some examples: 7k^2-4k+8 (5)2^k+3k-7

c) Suppose you draw the decision tree for mergesort when applied to an array of 2k elements. What will be the exact length of the shortest path in the tree? (Assume that the optimization described above is not being used.)

Your answer should be a formula in which k is the only variable. Simplify your formula as much as possible and express it using standard mathematical notation. Use ^ as the exponentiation operator. Your formula cannot contain summations. Write your formula as a sum or difference of terms, with higher order terms appearing before lower order terms. Include no spaces. Indicate multiplication, not by using a multiplication symbol. Use parentheses only where your formula would mean something else if you left them out. Here are some examples: 7k^2-4k+8 (5)2^k+3k-7 d) Suppose you draw the decision tree for mergesort when applied to an array of 2k elements. What will be the exact length of the shortest path in the tree? (Assume that the optimization described above is being used.) Your answer should be a formula in which k is the only variable. Simplify your formula as much as possible and express it using standard mathematical notation. Use ^ as the exponentiation operator. Your formula cannot contain summations. Write your formula as a sum or difference of terms, with higher order terms appearing before lower order terms. Include no spaces. Indicate multiplication, not by using a multiplication symbol. Use parentheses only where your formula would mean something else if you left them out. Here are some examples:

I know A is 5, 4, 3 respectively and B is (k-1)2^k+1, but I cannot figure out c or d for the life of me. I would prefer to know the answer for d if you can only answer one question. Thank you!