Homework 1: Asymptotic Analysis

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$  
b) $0.00001n^2$ $2^{2^{10}} (n \log n)$  
c) $5 n^{20} + n^2\log_2 n$ $n !$  
d) $4 n$ $4 \log_2 (2^n)$  
e) $5 n \log n$ $2 n^{1.5}$  
f) $7 n^{1024}$ $1.000001^n$  
g) $\frac{2 n^2}{\log n}$ $3 n$  

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($                   $)$  
$\Theta($                   $)$  
$\Theta($                   $)$  
$\Theta($                   $)$  
$\Theta($                   $)$  
$\Theta($                   $)$  
$\Theta($                   $)$  

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) {
            return 0;
        }  

        for (int j = 0; j < array.length; j++) {
            result += 1;
            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 $\Theta$ complexity class:

Code Listing B

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

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

    for (int j = array1.length-1; j >= 0; j--) {
        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 $\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 * 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 $\Theta$ complexity class:

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$.

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.)