Homework 2: Asymptotics

Handed out Thursday, September 22. Due at the start of class Tuesday, October 4, 2011 .

Problem 1.

Use the formal definitions (not the Limit Rule) to establish the following. In each case state specific values of the constants (e.g., $c_1$, $c_2$, $n_0$) you used to satisfy the conditions, and show how you arrived at these values. (There are many potentially correct choices. Explaining your work is thus essential for full credit.)

(a)

$4n^2 + 4n + 12 \in O(n^2 - 4n + 8)$

(b)

$2n^3 - 3n^2 + 17n \in \Theta(n^3)$.

(c)

$n^2 + 10n\lg^2 n \in O(n^2)$. (Hint: Find $n_0$ such that $\lg^2 n \le n$, for all $n \ge n_0$.)

Problem 2.

Repeat Problem 1, but this time use the Limit Rule to show that each function is in the set given in the problem.

Problem 3.

For each pair of expressions $(A,B)$ below, indicate whether $A$ is $O$, $o$, $\Omega$, $\omega$, or $\Theta$ of $B$. Note that zero, one or more of these relations may hold for a given pair; list all correct ones, and explain your work for partial credit.

$\begin{array}{lcc} & A & B \\ (a) & n^{200} & 4^n \\ (b) & (\log n)^{16} & \... .../4)} \\ (d) & 16^n & 65536^n \\ (e) & n^{\log n} & (\log n)^n \\ \end{array}$

Problem 4.

Consider the following algorithm to sort the array Keys.

for i=  1 to n-1 do
    base_j = i;
    base_x = Keys[i]
    for j = i + 1 to n do
        If Keys[j] < base_x then
            base_j = j;
            base_x = Keys[j];
    end forj;
    If base_j < > i then
       Keys[base_j] = Keys[i];
       Keys[i] =base_x;
end fori;

(a)

Give a summation for the number of key swaps in the worst case and simplify your summation.

(b)

Give a summation for the number of key swaps in the best case and simplify your summation.

(c)

Give a double summation for the number of comparisons in the worst case and simplify your summation.

(d)

Give a double summation for the number of comparisons in the best case and simplify your summation.

(e)

Give a double summation for the number of comparisons in the average case, but do not solve.