Comparing Functions (7 points)

For the following pairs of functions, indicate whether the ?? could be replaced with \(O\), \(\Omega\) or \(\Theta\). More than one may be applicable.

Orders of Functions (7 points)

List each of the functions from the previous problem from slowest to fastest growing in a table like the table below (include both the \(f(n)\) and \(g(n)\) functions). Group the functions by complexity class. Indicate which functions are in the same complexity class (same big-\(\Theta\) set).

NOTE: The number of rows in the table above may not match the number of complexity classes required.

Analyzing Java Code (12 points)

For each of the following Java methods, analyze the running time by:

1. writing an expression in terms of \(n\) for the every-time case analysis \(T(n)\) (if it exists) or worst case analysis \(W(n)\) (if the every-time case analysis does not exist) for the number of arithmetic operations,
2. give the appropriate big-\(\Theta\) complexity class for your analysis function \(T(n)\) or \(W(n)\).

Code Listing A

    public int A(int[] array) {

        int result = 10;
        int i = array.length;

        while (i > 1) {
            if (array[i - 1] < 0) {
                return 0;
            }

            for (int j = 0; j < array.length; j++) {
                result += 3 * array[j];
            }

            i = i / 2;
        }

        return result;
    }

1. Give your equation for \(T(n)\) or \(W(n)\) (which did you choose and why)?
2. Give the big-\(\Theta\) complexity class:

Code Listing B

    public int B(int[] array1) {
        int result = 0;

        for (int i = array1.length - 1; i >= 0; i--) {
            result += array1[j] * 10;
        }

        for (int j = 0; j < array1.length; j += 2) {
            result += array1[j] * 3;
        }

        return result;
    }

1. Give your equation for \(T(n)\) or \(W(n)\) (which did you choose and why)?
2. Give the big-\(\Theta\) complexity class:

Code Listing C

    public int C(int[] array1) {
        int result = 0;
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1.length; j++) {
                for (int k = 1; k < array1.length; k = k * 2) {
                    result += j * array1[k] + array1[i] + array1[j];
                }
            }
        }
        return result;
    }

1. Give your equation for \(T(n)\) or \(W(n)\) (which did you choose and why)?
2. Give the big-\(\Theta\) complexity class:

Which Algorithm? (2 points)

Consider the following two algorithms: Algorithm A requires \(14 n\log_2 n + 4\) steps to complete on an input of size \(n\). Algorithm B requires \(n^2\) steps. For what values of \(n\) should we prefer algorithm A? For what values of \(n\) should we prefer algorithm B? Justify your answer.

Demonstrating Big-\(\Theta\) (4 points)

Use either formal definition of big-\(\Theta\) to demonstrate that \(5n^3 + n \in \Theta(n^3)\).

Submitting

Use an appropriate typesetting program to produce a PDF of your solutions and submit them via the turn-in link on Canvas. (We encourage you to used LaTeX, but are not requiring it for this submission. Overleaf is a relatively user-friendly cloud-based LaTeX editor.)