Complexity Analysis

Question 1 (10)

(a) $f(n)=O(g(n))$ iff $\exists c>0,\ n_0>0$ such that $0 \le f(n) \le c\,g(n)$ for all $n \ge n_0$. (2) (why: bounds growth above beyond a threshold.)

(b) For $n \ge 1$: $5n \le 5n^2$ and $7 \le 7n^2$, so $3n^2 + 5n + 7 \le 3n^2 + 5n^2 + 7n^2 = 15n^2.$ Choose $c = 15$, $n_0 = 1$. Then $3n^2+5n+7 \le 15n^2$ for all $n\ge 1$. (5) (1 for bounding each lower term by an $n^2$ term, 2 for exhibiting $c,n_0$, 2 for the final inequality.)

(c) $2^{n+1} = 2\cdot 2^n \le 2\cdot 2^n$, so $c=2$, $n_0=1$ works → $O(2^n)$. (1.5) $2^{2n} = (2^n)^2$. Suppose $2^{2n} \le c\,2^n$; then $2^n \le c$ for all large $n$ — impossible since $2^n \to \infty$. Hence $2^{2n} \neq O(2^n)$. (1.5)

Question 2 (10)

(a) (3)

LinearSearch(A, n, x):
    for i = 0 to n-1:
        if A[i] == x:        # comparison counted here
            return i
    return -1

(comparison incurred once per loop iteration.)

(b) Best case: $x$ at index 0 → 1 comparison. Worst case: $x$ at last index (or absent) → $n$ comparisons. (3)

(c) If $x$ is at position $i$ (1-indexed), comparisons $= i$. Each position equally likely, probability $1/n$: $E[C] = \sum_{i=1}^{n} \frac{1}{n}\cdot i = \frac{1}{n}\cdot\frac{n(n+1)}{2} = \frac{n+1}{2}.$ (4) (2 for summation setup, 2 for closed form.) This is $\Theta(n)$.

Question 3 (12)

Here $n^{\log_b a}$ is the watershed.

(a) $a=2,b=2$: $n^{\log_2 2}=n^1=n$. $f(n)=n=\Theta(n)$ → Case 2. $\boxed{T(n)=\Theta(n\log n)}$. (3)

(b) $a=4,b=2$: $n^{\log_2 4}=n^2$. $f(n)=n=O(n^{2-\epsilon})$ → Case 1. $\boxed{T(n)=\Theta(n^2)}$. (3)

(c) $a=3,b=2$: $n^{\log_2 3}\approx n^{1.585}$. $f(n)=n^2 = \Omega(n^{\log_2 3 + \epsilon})$ and regularity holds ($3(n/2)^2 = \tfrac34 n^2 \le c n^2$) → Case 3. $\boxed{T(n)=\Theta(n^2)}$. (3)

(d) $a=2,b=2$: $n^{\log_2 2}=n$. $f(n)=n\log n$ is larger than $n$ but not by a polynomial factor $n^\epsilon$ (only by $\log n$), so Case 3 fails; it's not $\Theta(n)$ so Case 2 fails; not polynomially smaller so Case 1 fails. Using the extended case / recursion tree: $T(n)=\Theta(n\log^2 n)$. (3)

Question 4 (12)

(a) Tree for $T(n)=2T(n/2)+n$: (5)

• Level 0: cost $n$ (1 node).
• Level 1: 2 nodes, each $n/2$ → total $n$.
• Level $k$: $2^k$ nodes, each $n/2^k$ → total $n$.
• Depth: $n\to n/2\to\dots\to 1$ gives $\log_2 n$ levels.
• Total $= n\cdot(\log_2 n + 1)$.

(b) $T(n) = n\log_2 n + n = \Theta(n\log n)$. (2)

(c) Claim $T(n) \le c\,n\log_2 n$ for suitable $c$, $n\ge 2$. (5) Hypothesis: assume $T(n/2) \le c\,(n/2)\log_2(n/2)$. $T(n) = 2T(n/2)+n \le 2\cdot c\,\tfrac{n}{2}\log_2\tfrac{n}{2} + n = c n(\log_2 n - 1) + n$ $= c n\log_2 n - cn + n \le c n\log_2 n \quad\text{provided } c \ge 1.$ So with $c=1$ the induction step holds. (1 for stating hypothesis, 2 for substitution, 2 for closing with the $-cn+n\le0$ condition.)

Question 5 (10)

(a) Over $n$ pushes, capacity doublings occur at sizes $1,2,4,\dots$ Copy costs sum to $\sum_{j=0}^{\lfloor\log_2 n\rfloor} 2^j < 2n.$ Plus $n$ unit insert costs. Total $< n + 2n = 3n = O(n)$; amortized $= 3n/n = O(1)$. (5) (3 for the geometric sum $<2n$, 2 for combining and dividing.)

(b) Charge 3 per push: 1 pays the immediate insert, 2 are saved as credit. When capacity doubles from $k$ to $2k$, the $k$ old elements each carry 2 saved credits → $2k$ credit available, enough to pay the $k$ copies. Credit never goes negative → amortized $O(1)$. (3)

(c) Let $\Phi(D_i) = 2\cdot(\text{num elements}) - (\text{capacity})$. It must satisfy $\Phi(D_0)=0$ and $\Phi(D_i)\ge 0$ for all $i$, so that $\sum \hat c_i \ge \sum c_i$ (amortized costs upper-bound actual total). (2)

Question 6 (6)

(a) $\Theta(g)$: $\exists c_1,c_2,n_0>0$ with $0\le c_1 g(n)\le f(n)\le c_2 g(n)$ for $n\ge n_0$. $\Omega(g)$: $\exists c,n_0>0$ with $0\le c\,g(n)\le f(n)$ for $n\ge n_0$. (2)

(b) Upper: $\tfrac12 n^2 - 3n \le \tfrac12 n^2$ → $c_2=\tfrac12$. (1.5) Lower: need $\tfrac12 n^2 - 3n \ge c_1 n^2$. Take $c_1=\tfrac14$: $\tfrac12 n^2 - 3n \ge \tfrac14 n^2 \iff \tfrac14 n^2 \ge 3n \iff n \ge 12$. (1.5) So $c_1=\tfrac14, c_2=\tfrac12, n_0=12$ gives $\Theta(n^2)$. (1)

[
  {"claim":"Average linear search comparisons = (n+1)/2 via sum i/n", "code":"n=symbols('n',positive=True); i=symbols('i'); expr=summation(i/n,(i,1,n)); result = simplify(expr-(n+1)/2)==0"},
  {"claim":"Bounding 3n^2+5n+7 <= 15n^2 at n0=1 holds", "code":"result = (3*1**2+5*1+7) <= 15*1**2"},
  {"claim":"Doubling copy cost sum 2^0..2^k < 2n (test n=16, k=4)", "code":"result = sum(2**j for j in range(0,5)) < 2*16"},
  {"claim":"Theta lower bound: n^2/2-3n >= n^2/4 for n>=12", "code":"n=12; result = (n**2/2-3*n) >= (n**2/4)"}
]