Comparing Functions (14 points)

For the following pairs of functions, indicate whether the ?? could be replaced with $O$, $\Omega$ or $\Theta$.

Pr.	$f(n)$	$g(n)$	$f(n) \in ?? (g(n))$
a)	$48 n$	$2 n^2 + 1$	$O$
b)	$0.00001n^2$	$2^{2^{10}} (n \log n)$	$\Omega$
c)	$5 n^{20} + n^2\log_2 n$	$n !$	$O$
d)	$4 n$	$4 \log_2 (2^n)$	$\Theta$
e)	$5 n \log n$	$2 n^{1.5}$	$O$
f)	$7 n^{1024}$	$1.000001^n$	$O$
g)	$\frac{2 n^2}{\log n}$	$3 n$	$\Omega$

Orders of Functions (14 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).

Complexity class	Functions from previous problem.
$\Theta(n)$	$48n$, $4n$, $4\log_2 (2^n)$, $3n$
$\Theta(n\log n)$	$2^{2^{10}}(n\log n)$, $5n\log n$
$\Theta(n^{1.5})$	$2 n^{1.5}$
$\Theta(n^2)$	$0.00001n^2$, $2n^2 + 1$
$\Theta(\frac{n^2}{\log n})$	$\frac{2n^2}{\log n}$
$\Theta(n^{20})$	$5n^{20} + n^2\log_2 n$
$\Theta(n^{1024})$	$7n^{1024}$
$\Theta(1.000001^n)$	$1.000001^n$
$\Theta(n!)$	$n!$

NOTE: You may not need all of the rows in the table above.

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 = 25;
    int i = array.length;

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

        for (int j = 0; j < array.length; j++) {
            result += 1;
            result += 3 * array[j];
        } // 4 operations per iteration, 4n per iteration of outer loop

        i = i / 2; // 1 op

        // So this loop does 2 + 4n operations each iteration
    } // This occurs (log n + 1) times, though we are flexible if you got (log n)

    return result;
}

1. Give your equation for $T(n)$ or $W(n)$ (which did you choose and why)? $W(n) = (\log n + 1) (4n + 2) = 4n \log n + 4n + 2\log n + 2$. We used $W(n)$ because there is no every-case time complexity since the if statement in the loop exits the method early in the event that array[i-1] < 0.
2. Give the $\Theta$ complexity class: $\Theta(n\log n)$

Code Listing B

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

    for (int i = 0; i < array1.length / 2; i++) {
        result += array1[i] * 2;
    } // 4 ops per iteration plus one extra divide, n/2 iterations, total : 4n/2 + 1 = 2n + 1

    for (int j = array1.length-1; j >= 0; j--) {
        result += array1[j] * 3;
    } // 3 ops per iteration, plus one extra for initialization of j, so 3n + 1

    return result;
}

1. Give your equation for $T(n)$ or $W(n)$ (which did you choose and why)? $T(n) = 5n + 2$. Every-time case because loop iteration count doesn’t depend on input values.
2. Give the $\Theta$ complexity class: $\Theta(n)$

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 * j * array1[k] + array1[i] + array1[j];
            } // 6 ops per iteration, log n + 1 iterations: 6log n + 6 total
        } // 6log n + 7 ops per iteration, n iterations, 6 n log n + 7 n total
    } // 6 n log n + 7n + 1 ops per iteration, n iterations, 6n^2 log n + 7n^2 + n ops total
    return result;
}

1. Give your equation for $T(n)$ or $W(n)$ (which did you choose and why)? $T(n) = 6 n^2\log n + 7 n^2 + n$ (Every-time since it doesn’t depend on the values of array1, just the length.)
2. Give the $\Theta$ complexity class: $\Theta(n^2\log n)$.

How much faster? (6 points)

Suppose you have an algorithm that performs $T(n) = 8 n^3$ arithmetic operations on an input of size $n$. Suppose you have two machines, machine A and machine B. Machine A performs 10 arithmetic operations per second, while machine B performs 20 arithmetic operations per second.

1. What is the largest input size $n_A$ you can compute on machine A in 60 seconds?
2. What is the largest input size $n_B$ you can compute on machine B in 60 seconds?
3. Write an equation describing the relationship between $n_A$ and $n_B$.

The easiest way to solve this is to recognize that if machine A runs 10 ops per second and we run it for 60 seconds, then it will have performed 600 ops. Thus we are asking for what value of $n_A$ is $8 n_A^3 = 600$. Solving for $n_A$ we get $n_A = \sqrt[3]{75}$.

If machine B runs in 20 ops per second, and we run it for 60 seconds, then it performs 1200 ops. Thus $8 n_B^3 = 1200$. Solving for $n_B$ we get $n_B = \sqrt[3]{150}$.

Finally, notice that $8 n_A^3 = 600$ and $8 n_B^3 = 1200$. Thus $8 n_B^3 = 1200 = 2 * 600 = 2 (8 n_A^3)$. Solving for $n_B$ we get that $n_B^3 = 2 n_A^3 \Rightarrow n_B = \sqrt[3]{2} n_A \approx (1.26 n_A)$. In other words, if we double the speed of our machine, the size of the problem we can solve in a fixed time frame only increases by a factor of $1.26$.