1. Do the following problems:

a) Explain in your words, what each of the following mean: (Be sure to use the rules of complexity, complexity algebra).

(x1) 4n + 6 ~ O(n2);

(x2) 5n2 3n + 6 ~ (n)

(x3) 5n2 3n + 6 ~ (n2)

Say: f(n) has complexity [O(g(n)) | (g(n)) | (g(n))].

b) For f(n) = n5/4 + 6n, g(n) = 50n5 + n2 + n, indicate whether f(n) ~ O(g(n)), f(n) ~ (g(n)), or f(n) ~ (g(n)). Explain.

c) For f(n) = 2n, g(n) = 3n, indicate whether f(n) ~ O(g(n)), f(n) ~ (g(n)), or f(n) ~ (g(n)). Explain.

d) What is the run time complexity, based on N, of the following code fragment?

for (i = 0; i < N; i++)

for(j = 0; j < N; j++)

for (k = 0; k < N; k++)

cin >> A[i][j][k];