Due Date: Monday, October 23, 2023.

This is a written homework dealing with algorithm complexity analysis. You can use a document (Word or pdf) to submit it, or write it on paper and scan it or take pictures of it to submit.

For each of the program fragments below, compute the complexity T(n) as a precise count of basic operations, using the model seen on pages 5 and 9 in the slides. After that, state what the algorithm is big Oh or big Theta of. Provide separate best case and worst case scenarios when appropriate.

a.

sum = 0;
for (int i = 0; i < n; i++)
    if (i % 2 == 0)
        sum++;

b.

sum = 0;
for (int i = 0; i < n; i += 3)
    sum++;

c. Consider n = a.length.

found = false;
for (int i = 0; i < a.length; i++)
    if (a[i] == value)
        found = true;

For each of the program fragments below, figure out the total number of iterations for the loops involved. Use that information to state what the algorithm is big Oh or big Theta of.

a.

sum = 0;
for (int i = 1; i < n; i++)
    sum++;

b.

sum = 0;
for (int i = 0; i < 4 * n; i ++)
    sum++;

c.

sum = 0;
for (int i = n; i > 0; i--)
    sum++;

d.

sum = 0;
for (int i = 0; i < n * n; i++)
    for (j = 1; j < n; j = j * 2)
        sum++;

An algorithm takes 0.5ms for an input of size 100. How long will it approximately take for an input size 500 if the running time is the following?

• a. linear
• b. quadratic
• c. cubic

Upload the homework files to Canvas - Assignments - Homework 7.