HW 2

Wed, Sep 16, 2015

Homework 2: Asymptotic Analysis

Your answers to the following exercises should be submitted through Canvas as a single hw02.pdf file. Equations should be properly formatted using equation editing software, such as $\LaTeX$ or the equation editor in MS Word or LibreOffice. An example $\LaTeX$ starter document can be found here.

1. Analyze C Algorithms (9 pts. total)

Analyze the running time of each of the following three C functions. Each of the functions takes as input an integer array arr and its length n. For each function you should give the running time $T(n)$ as a function of $n$ and then give the appropriate Big-O classification. (3 pts. each)

NOTE: For the purposes of this problem, integer addition and multiplication are the only basic operation that you should count when determining the running time $T(n)$ (i.e. you can ignore array accesses, assignments, etc.). You can assume for simplicity that $n$ is divisible by 2.

int A(int arr[], int n) 
{
	int result = 25;

	int i = n;
	while (i > 1) {
		for (int j = 0; j < n; j++) {
			result += 1;
			result += 3 * arr[j];
		}
		i = i / 2;
	}
	
	return result;
}

int B(int arr[], int n) 
{
	int result = 0;
	
	for (int i = 0; i < n/2; i++) {
		result += 3 * arr[i];
	}
	
	for (int i = n/2; i < n; i++) {
		result += 4 * arr[i];
	}
	
	for (int i = n-1; i >= 0; i--) {
		result += 3 * arr[i];
		result += 5 * arr[i];
	}
	
	return result;

}

int C(int arr[], int n)
{
	int result = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < n; k++) {
				result += j * j + arr[k];
			}
		}
	}
	return result;
}

2. Comparing Functions (14 pts. total)

For the following pairs of functions, indicate whether the ?? could be replaced with O, $\Omega$, or $\Theta$. More than one may be correct: indicate all that apply. (2pts each)

Pr.	$f(n)$	$g(n)$	$f(n)$ is ?? $(g(n))$
a)	$.00001n^4$	$375 \log_2 n$
b)	$24 n$	$2n^2 + 1$
c)	$ 3n^3 + 2n $	$2^n$
d)	$6n$	$\log_2 n$
e)	$n!$	$5 n^{20} + n^2 \log_2 n$
f)	$3n$	$3 \log_2 (2^n)$
g)	$95 n + 2$	$3 n + \log_2 n$

3. Orders of Functions (14 pts. total)

List each of the functions from #2 from slowest to fastest growing in a table like the table below. Group the functions by complexity class. Indicate which functions are in the same complexity class (same big-$\Theta$).

Complexity Class	Functions from #2 in class

NOTE: You may need fewer rows than provided.

4. Comparing algorithms. (1 pt.)

Consider the following two algorithms: Algorithm A requires $8n+24$ steps to copmlete on an input of size $n$. Algorithm B requires $2n^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.

5. Proof of Big-$\Theta$ (2 pts.)

Using either definition of Big-$\Theta$, demonstrate that $3 n^4 + 2 n^2 + 3$ is $\Theta(n^4)$.