Due Date: Monday, March 7, 2022.

This is a written homework dealing with algorithm complexity analysis. You can use a Word document or simple text 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 a table such as the ones in the lecture slides for the first 4 examples. Start by identifying the number of iterations for each loop and total, then write each basic operation on a row and next to it the count. Finally, compute the total count and figure out the big O or big Theta for the resulting function. Provide separate best case and worst case scenarios when appropriate.

a. Given an array a of size n

k = 0;
for (int i = 0; i < a.length; i++)
    if (a[i] == target)
        k++;

b.

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

c. Consider n = a.length.

for (int i = 0; i < a.length-1; i++)
    if (a[i] < a[i+1])
        return false;
return 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.

k = 0;
for (int i = 0; i < n; i += 2)
    for (int j = n; j > 0; j--)
        k++;

b.

for (i = 0; i < n; i++)
    for (j = 0; j < n; j++) {
        c[i][j] = 0;
        for (k = 0; k < n; k++)
            c[i][j] += a[i][k] * b[k][j];
    }

c.

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

Complete the following exercises from the notes, chapter 4:

• 4-6
• 4-12
• 4-34
• 4-46

Upload documents or image files to Canvas - Assignments - Homework 7.