1. Consider the polynomial P(n) of degree k:

P(n) = a_kn^k + a_k-1n^k-1+..+ a₁n + a₀. with all a_i > 0

Using the definition of (n^k), prove that

P(n) (n^k).

2. List all the functions below from the lowest to the highest order (in terms of growth). If functions have similar growth () , group them between brackets ([]). Brief justifications are ok.

n 2ⁿ nlg(n) ln(n) lg(n) sqrt(n) n² + lg(n)

eⁿ n² 2^n-1 lg(lg(n)) n³ (lg(n))² n! n n⁴ + 7n⁶

Consider this algorithm:

a = 0

for i=0 to n

for j=i+1 to n

a = a + 2

The objective is to find the total number N of additions performed by the above algorithm to execute the statement a = a + 2. Inspire yourself from the analysis of the nave 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 (growth) for N.