Why does the lower-order terms NOT matter in the asymptotic notation of algorithm runtime?

A. Because we only care about the exact number of steps given an input.

B. Because we only care about the small inputs.

C. Because we only care about the growth rate of the number of steps as the input becomes larger.

D. Because we only care about the large input

Consider the following function with a loop:

// Pre: n > 0 is a natural number // Post: returns the value of n^2 int square(int n) { r = 0; k = 0; while (k < n) { r = r + 2 * k + 1; k = k + 1; } return r; }

Is k < n a valid loop invariant? Why or why not? Choose one from below.

A.

k < n is a valid loop invariant because it is true as long as we're in the loop

B.

k < n is NOT a valid loop invariant because it is not true before entering the loop

C.

k < n is NOT a valid loop invariant because it is always false.

D.

k < n is NOT a valid loop invariant because it is not true at the ends of all iterations