This a question on algorithm and has multiple parts. Please read carefully and answer them with clear explanations. Thank you.

Question 3 (25-+9+9 points): (a) What is the input size of the following algorithm and why? What does the algorithm compute? Write the output mathematically as a function of n. Derive the complexity of the algorithm carefully (show all steps). Is it a polynomial time algorithm ? If you say yes, prove it carefully. If you say no, please give a polynomial time algorithm for computing the same input-output relationship Input: A natural number n > 1 Algorithm Mystery(n) f int sum 0; int i=1; while i