1) Show that 6n² + 20n is big-Oh of n³, but not big-Omega of n³. You can use either the definition of big-Omega (formal) or the limit approach

2) Show that n³ is big-Omega of n². You can use either the definition of big-Omega (formal) or the limit approach.

3) Consider the following algorithm:

int j = 1;

int k = 1;

for (i = 1; i <= 10; i++)

j = j * 100;

for (i = 1; i <= 20; i++)

k = k * 2;

What is the running time, T(n)? Give both the exact function T(n), and then give a big- Theta estimate of T(n). Show your work. For example, if T(n) is exactly n² + 3n, then T(n) is big-Theta of n².

4) Consider the following algorithm:

int k = 0;

for (i = 2; i <= n; i++)

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

k = i + j;

What is the running time, T(n)? Give both the exact function T(n), and then give a big- Theta estimate of T(n).

5) If the worst case time of algorithm A is big-oh of that of B, then B is not faster than A for large problems. (True or False) Explain! Then consider if A is strictly big-oh, how about then?

6) n⁴ is big-oh of n^6. (True or False)

7) Since 2(2n + 5) >= 3n for n >= 0, and 3n >= 2n + 5 for n >= 5, 2n + 5 is big-oh of 3n. (True or False)

8) If f(n) is big-theta of g(n), then the value of f may be infinitely away from that of g. (True or False)