Homework Chapter 1

1. Justify your answer to the following using formal definitions for theta, big O, or Omega. Use either the limit or the constant definition:

a. Show 3n⁵ + 4n⁴ +3n + 3 belongs to theta of (n⁵)

b. Does 4n³ + 3 belongs to O (n²)

c. Does 2n² belongs to O (n³)

d. Does 2n² belongs to theta of (n³)

e. Show n⁴ + 3n² +4n belongs to omega of (n³)

2. Given the following algorithm:

y = 1;

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

{

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

{

x = A[i] + A[j];

x = x * y;

}

y = y + x;

}

Assume all variables are properly declared.

a. How many additions are done in the worst case?

b. How many multiplications are done in the worst case?

c. Is the average case different than the worst case? Justify your answer.

d. What is the exact growth rate of the algorithm (theta)?

3. Question 14