Homework 1: Asymptotic Analysis

James Madison University, Spring 2019

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.

Pr.	$f(n)$	$g(n)$
a)	$6 n$	$n^2 + 2$
b)	$0.00001n^2$	$2^{2^{100}} (n \log n)$
c)	$5 n^{20} + n^2\log_2 n$	$n !$
d)	$4 n$	$4 \log_2 (2^n)$
e)	$2 n^{1.5}$	$5 n \log n$
f)	$1.000001^n$	$7 n^{1024}$
g)	$\frac{2 n^2}{\log n}$	$4 n$

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

Complexity class	Functions from previous problem.
$\Theta($ $)$
$\Theta($ $)$
$\Theta($ $)$
$\Theta($ $)$
$\Theta($ $)$
$\Theta($ $)$
$\Theta($ $)$

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:

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,
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;
    }

Give your equation for $T(n)$ or $W(n)$ (which did you choose and why)?
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 / 2; j++) {
            result += array1[j] * 3;
        }

        return result;
    }

Give your equation for $T(n)$ or $W(n)$ (which did you choose and why)?
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;
    }

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

Which Algorithm? (2 points)

Consider the following two algorithms: Algorithm A requires $14n + 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 $2n^3 + 2n^2 \in \Theta(n^3)$ .

Submitting