Please solve and justify your answer

Exercise 3 (25 points) Consider the polynomial P(n) of degree k: P(n) = an + ak,,nk-4 + ain + 24, with all a.>0 Using the definition of O(n), prove that P(n) O(n) Exercise 4 (25 points) List all the functions below from the lowest to the highest order n 2 nlg(n) In(o) gn) srtn) n2+ g(n) Exercise 5 (20 points) Consider this algorithm: for i-0 to n for j-1+1 to a-a2 n The objective is to find the number N, of additions performed by the statement aa+2. Inspire yourself from the analysis of the naive sorting algorithm to: 1) Express N, as a function of n. 2) Express the final value of a when the algorithm ends 3) Provide the best bound for N