Complexity Analysis

Question 1

(a) $f(n)=O(n^2)$ (6 marks)

Definition: $f=O(g)$ iff $\exists c>0, n_0\ge1$ with $0\le f(n)\le c\,g(n)$ for all $n\ge n_0$. (1)

For $n\ge 1$: $\log_2 n \le n$, so $5n\log_2 n \le 5n^2$; also $7\le 7n^2$. (2) Hence $f(n)=3n^2+5n\log_2 n+7 \le 3n^2+5n^2+7n^2 = 15n^2.$ (2) Take $c=15$, $n_0=1$. The inequality $f(n)\le 15n^2$ holds for all $n\ge1$, proving $f=O(n^2)$. (1)

(b) $\Omega$ and hence $\Theta$ (4 marks)

Since all terms of $f$ are positive for $n\ge1$, $f(n)\ge 3n^2$. (2) Thus with $c'=3$, $n_0=1$: $f(n)\ge 3n^2$, giving $f=\Omega(n^2)$. (1) $f=O(n^2)$ and $f=\Omega(n^2)$ $\Rightarrow f=\Theta(n^2)$. (1)

(c) Is $5n\log_2 n = O(n^{1.5})$? — FALSE (4 marks)

Consider $\lim_{n\to\infty}\frac{5n\log_2 n}{n^{1.5}}=\lim_{n\to\infty}\frac{5\log_2 n}{n^{0.5}}.$ (2) As $n\to\infty$, $\log_2 n$ grows slower than any positive power, so $\dfrac{\log_2 n}{\sqrt n}\to 0$. (1)

Wait — this limit is $0$, which would make it TRUE. Correct evaluation: $\log_2 n = o(n^{0.5})$, so $n\log_2 n = o(n^{1.5})$, hence $5n\log_2 n = O(n^{1.5})$ is TRUE. (1 for correct conclusion)

Correct conclusion: the claim is TRUE. The limit above tends to $0$, so $5n\log_2 n\in o(n^{1.5})\subseteq O(n^{1.5})$. Full marks require identifying the limit $=0$ and concluding TRUE.

(d) $\Theta$ is an equivalence relation (4 marks)

Write $f\sim g$ for $f=\Theta(g)$.

• Reflexive: $f(n)\le 1\cdot f(n)$ and $f(n)\ge 1\cdot f(n)$, so $f=\Theta(f)$. (1)
• Symmetric: $f=\Theta(g)$ means $c_1 g\le f\le c_2 g$ eventually. Dividing: $\frac1{c_2}f\le g\le \frac1{c_1}f$, so $g=\Theta(f)$. (1.5)
• Transitive: if $c_1 g\le f\le c_2 g$ (for $n\ge n_1$) and $d_1 h\le g\le d_2 h$ (for $n\ge n_2$), then for $n\ge\max(n_1,n_2)$: $c_1 d_1 h \le f \le c_2 d_2 h$, so $f=\Theta(h)$. (1.5)

Question 2

(a) Why Master Theorem stalls (3 marks) Here $a=2$, $b=2$, so $n^{\log_b a}=n^{\log_2 2}=n$. The driving term is $f(n)=n\log_2 n$, which is not $\Theta(n^c)$ for any constant $c$: it lies between $n$ and $n^{1+\varepsilon}$. (2) The polynomial three-case version fails; we use the extended Case 2: if $f(n)=\Theta(n^{\log_b a}\log^k n)$ then $T(n)=\Theta(n^{\log_b a}\log^{k+1}n)$. Here $k=1$. (1)

(b) Recursion tree (7 marks) Root work: $n\log_2 n$. (1) At depth $i$ there are $2^i$ nodes, each of size $n/2^i$; work per node $=\frac{n}{2^i}\log_2\frac{n}{2^i}$. (2) Total work at level $i$: $2^i\cdot\frac{n}{2^i}\log_2\frac{n}{2^i}=n\bigl(\log_2 n - i\bigr).$ (2) Number of levels: $n/2^L=1\Rightarrow L=\log_2 n$. Summing $i=0$ to $\log_2 n-1$: $\sum_{i=0}^{\log_2 n-1} n(\log_2 n - i)=n\sum_{j=1}^{\log_2 n} j = n\cdot\frac{\log_2 n(\log_2 n+1)}{2}=\Theta(n\log_2^2 n).$ (2) (The leaf level contributes $\Theta(n)$, dominated.) Conclusion: $T(n)=\Theta(n\log_2^2 n)$.

(c) Substitution — upper bound (6 marks) Guess $T(n)\le c\,n\log_2^2 n$. Inductive step, assuming it for $n/2$: $T(n)=2T(n/2)+n\log_2 n \le 2c\frac n2\log_2^2\!\frac n2 + n\log_2 n = c\,n(\log_2 n-1)^2+n\log_2 n.$ (2) Expand: $c\,n(\log_2^2 n - 2\log_2 n + 1)+n\log_2 n = c\,n\log_2^2 n - 2c\,n\log_2 n + c\,n + n\log_2 n.$ (2) This is $\le c\,n\log_2^2 n$ provided $-2c\,n\log_2 n + c\,n + n\log_2 n \le 0 \iff (1-2c)\log_2 n + c \le 0.$ For $c\ge 1$ this holds for all $n\ge 2$ (since $1-2c<0$ and the $\log$ term dominates). Take $c=1$, $n_0=2$; base case $T(2)=2T(1)+2=4\le 1\cdot2\cdot1=2$ fails, so pick $c=2$ giving $c\cdot2\cdot1=4\ge4$. ✓ (2) Hence $T(n)=O(n\log_2^2 n)$, matching the tree bound.

(d) Decrease-by-constant (2 marks) $S(n)=\sum_{k=1}^n k=\frac{n(n+1)}2=\Theta(n^2)$. (2)

Question 3

(a) Aggregate method (5 marks) Insertions cost $1$ each: total $n$. (1) Doublings occur when size hits $1,2,4,\dots$; copy costs are $1+2+4+\cdots+2^{\lfloor\log_2(n-1)\rfloor} < 2^{\lceil\log_2 n\rceil}\le 2n$. (2) Geometric series: $\sum_{k=0}^{\lfloor\log_2 n\rfloor}2^k = 2^{\lfloor\log_2 n\rfloor+1}-1 < 2n$. (1) Total cost $< n+2n=3n$, so amortized cost $<3n/n=3=O(1)$. (1)

(b) Accounting method (4 marks) Charge $\hat c=3$ per push. (1) Actual insertion uses 1; store 2 credits on the newly inserted element (and, effectively, the "just-copied" region). (1) When the array of size $m$ doubles, the $m$ elements copied were each charged 2 extra credits since the previous doubling, which exactly pays the $m$ copy operations. (1) Balance never negative $\Rightarrow$ amortized cost $=3=O(1)$. (1)

(c) Potential method (3 marks) Define $\Phi(D_i)=2\cdot(\text{size}) - (\text{capacity})$. (1) Then $\Phi(D_0)=0$ (size 0, cap... take convention $\Phi=0$ initially) and $\Phi\ge0$ since after any doubling size $\ge$ capacity/2 so $2\,\text{size}\ge\text{capacity}$. (1) Amortized cost $\hat c_i=c_i+\Phi(D_i)-\Phi(D_{i-1})$: non-doubling push: $c_i=1$, size$+1$ so $\Delta\Phi=2$, total $3$. Doubling push (size $m\to m{+}1$, cap $m\to2m$): $c_i=m+1$, $\Delta\Phi=(2(m{+}1)-2m)-(2m-m)=2-m$, total $=m+1+2-m=3$. (1) Consistent $O(1)$.

(d) Physics analogy (2 marks) $\Phi$ acts like stored potential/elastic energy: cheap operations "charge up" $\Phi$ (like charging a capacitor storing $\tfrac12CV^2$), and the rare expensive resize "discharges" it, so the stored energy pays for the burst. (1) Because the potential's contributions telescope, the long-run amortized (average) rate is $O(1)$ — the relevant metric for sustained throughput, just as average power, not instantaneous surge current, governs long-run behaviour. (1)

[
  {"claim":"f(n)=3n^2+5n log2 n+7 <= 15 n^2 for n=1..1000","code":"import sympy as sp\nok=all(3*n**2+5*n*sp.log(n,2)+7 <= 15*n**2 for n in range(1,1001))\nresult=bool(ok)"},
  {"claim":"limit of 5 log2 n / sqrt(n) is 0 (so 5 n log2 n = O(n^1.5))","code":"n=sp.symbols('n',positive=True)\nL=sp.limit(5*sp.log(n,2)/n**sp.Rational(1,2),n,sp.oo)\nresult=(L==0)"},
  {"claim":"recursion tree sum n*sum_{j=1}^{L} j equals n*L*(L+1)/2","code":"n,L=sp.symbols('n L',positive=True)\nj=sp.symbols('j')\nlhs=n*sp.summation(j,(j,1,L))\nresult=bool(sp.simplify(lhs - n*L*(L+1)/2)==0)"},
  {"claim":"S(n)=sum k = n(n+1)/2","code":"n=sp.symbols('n',positive=True,integer=True)\nk=sp.symbols('k')\nresult=bool(sp.simplify(sp.summation(k,(k,1,n)) - n*(n+1)/2)==0)"},
  {"claim":"aggregate doubling copies: sum_{k=0}^{m} 2^k = 2^(m+1)-1 < 2*2^m","code":"m=sp.symbols('m',nonnegative=True,integer=True)\nk=sp.symbols('k')\ns=sp.summation(2**k,(k,0,m))\nresult=bool(sp.simplify(s-(2**(m+1)-1))==0)"}
]