Level 4 — ApplicationComplexity Analysis

Complexity Analysis

⏱ 60 minutes50 marksprintable — key stays hidden on paper

Level: 4 — Application (novel problems, no hints) Time Limit: 60 minutes Total Marks: 50

Q1. [10 marks] A programmer writes a function on an array of size $n$ :

process(A, n):
    if n <= 1: return
    for i in 0..n-1:            # loop L1
        for j in 0..i:         # loop L2
            visit(A[j])
    process(A, n/3)
    process(A, n/3)

(a) Write the recurrence $T(n)$ for the running time in terms of the work done at each level and the recursive calls. [3]

(b) Solve $T(n)$ using the Master Theorem, stating $a$ , $b$ , and $f(n)$ , and identifying which case applies. [5]

Q2. [12 marks] Consider a dynamic array (initially capacity 1) that doubles its capacity when full, but on each doubling it copies all existing elements. Additionally, whenever the array becomes exactly one-quarter full after deletions, it halves its capacity (copying survivors).

(a) Using the aggregate method, prove that a sequence of $n$ push operations (no deletions) costs $O(n)$ total, and state the amortized cost per push. [5]

(b) Using the accounting method, assign a charge per push that pays for future copies. State the charge and justify it covers all copy work. [4]

(c) Explain in one or two sentences why the quarter-full (rather than half-full) shrink threshold prevents $O(n)$ amortized cost from thrashing between grow and shrink. [3]

Q3. [10 marks] Prove the following statements directly from the formal definition of the asymptotic notations (produce explicit constants where required).

(a) Prove $3n^2 + 5n + 2 = O(n^2)$ by exhibiting constants $c$ and $n_0$ . [3]

(b) Prove $3n^2 + 5n + 2 = \Omega(n^2)$ with explicit $c$ , $n_0$ . [3]

Q4. [10 marks] Solve the recurrence using the recursion tree method, then verify by substitution: $T(n) = 3\,T(n/4) + n, \qquad T(1) = 1.$

(a) Draw/describe the recursion tree: cost per level, number of levels, and total cost. [6]

(b) Verify your answer by the substitution method (guess $T(n) \le cn$ and find a valid $c$ ). [4]

Q5. [8 marks] For the algorithm below (searching for a target x in an unsorted array of $n$ distinct elements, each equally likely to be the target and target guaranteed present):

linsearch(A, x):
    for i in 0..n-1:
        if A[i] == x: return i

(a) State best-case and worst-case comparison counts with a one-line justification each. [3]

(b) Derive the average-case number of comparisons exactly (closed form), assuming uniform position distribution. [3]

Answer keyMark scheme & solutions

Q1 [10]

(a) Work in loops L1/L2: sum over $i$ of $(i+1) = \frac{n(n+1)}{2} = \Theta(n^2)$ . Two recursive calls of size $n/3$ : $T(n) = 2\,T(n/3) + \Theta(n^2). \quad \textbf{[3]}$

(b) Master theorem with $a=2$ , $b=3$ , $f(n)=\Theta(n^2)$ . [1] Compare $n^{\log_b a} = n^{\log_3 2} \approx n^{0.631}$ with $f(n)=n^2$ . [2] Since $f(n) = \Omega(n^{\log_3 2 + \varepsilon})$ and the regularity condition $2\,(n/3)^2 = \frac{2}{9}n^2 \le c\,n^2$ holds for $c=\frac{2}{9}<1$ , Case 3 applies. [2]

(c) $T(n) = \Theta(n^2)$ . [2]

Q2 [12]

(a) Copies occur at sizes $1,2,4,\dots,2^{\lfloor\log_2 n\rfloor}$ . Total copy work $\le 1+2+4+\dots+n < 2n$ . Plus $n$ units for the pushes themselves. Total $= n + (2n-1) = O(n)$ . [3] Amortized cost per push $= O(n)/n = O(1)$ (a small constant, $\le 3$ ). [2]

(b) Charge 3 per push: 1 for placing the element, 1 saved to move itself on the next copy, 1 saved to move an element that was moved for free previously. When array of size $k$ doubles, the $k/2$ elements added since the last doubling each carry 2 saved credits ⇒ $k$ credits, enough to copy all $k$ elements. [4]

(c) Halving only at quarter-full leaves the array half-full immediately after a shrink, so $\Theta(n)$ operations are required before either another grow or shrink is triggered — the copy cost is amortized over $\Theta(n)$ ops, avoiding thrashing (which a half-full shrink threshold would cause). [3]

Q3 [10]

(a) For $n\ge1$ : $3n^2+5n+2 \le 3n^2+5n^2+2n^2 = 10n^2$ . So $c=10,\ n_0=1$ . [3]

(b) $3n^2+5n+2 \ge 3n^2$ for all $n\ge1$ (extra terms positive). So $c=3,\ n_0=1$ . [3]

(c) Both $O(n^2)$ and $\Omega(n^2)$ ⇒ $\Theta(n^2)$ . [2] For $2^n \ne O(n^k)$ : $\lim_{n\to\infty} \frac{2^n}{n^k} = \infty$ (exponential beats any polynomial, provable by L'Hôpital $k$ times or ratio test). Hence no constants $c,n_0$ can bound $2^n \le c\,n^k$ for all large $n$ . [2]

Q4 [10]

(a) Root cost $n$ . Level $i$ has $3^i$ nodes each of size $n/4^i$ , cost per level $= 3^i \cdot n/4^i = n(3/4)^i$ . [2] Levels: $i=0\dots\log_4 n$ . [1] Total $= n\sum_{i=0}^{\log_4 n}(3/4)^i < n\cdot\frac{1}{1-3/4} = 4n$ . [2] So $T(n)=\Theta(n)$ . [1]

(b) Guess $T(n)\le cn$ . Then $T(n)=3T(n/4)+n \le 3\cdot c(n/4)+n = \frac{3c}{4}n + n = \left(\frac{3c}{4}+1\right)n$ . Need $\frac{3c}{4}+1 \le c \Rightarrow 1 \le c/4 \Rightarrow c\ge4$ . Take $c=4$ : holds. [4]

Q5 [8]

(a) Best case $=1$ (target at index 0). Worst case $=n$ (target at last index / not found early). [3]

(b) Average $=\frac{1}{n}\sum_{i=1}^{n} i = \frac{1}{n}\cdot\frac{n(n+1)}{2} = \frac{n+1}{2}$ . [3]

(c) Auxiliary space $=O(1)$ (only loop index / return value). Total space $=O(n)$ (includes the input array). Distinction: auxiliary excludes input storage; total includes it. [2]

[
  {"claim":"Q4 recursion tree geometric sum bounded by 4n, Theta(n)","code":"i=symbols('i'); S=summation((Rational(3,4))**i,(i,0,oo)); result=(S==4)"},
  {"claim":"Q4 substitution constant c=4 satisfies 3c/4+1<=c","code":"c=4; result=(Rational(3,4)*c+1<=c)"},
  {"claim":"Q5 average comparisons = (n+1)/2","code":"n=symbols('n',positive=True); k=symbols('k'); avg=summation(k,(k,1,n))/n; result=(simplify(avg-(n+1)/2)==0)"},
  {"claim":"Q3a bound 3n^2+5n+2 <= 10n^2 for n>=1","code":"n=symbols('n',positive=True); expr=10*n**2-(3*n**2+5*n+2); result=(expr.subs(n,1)>=0) and (simplify(diff(expr,n)).subs(n,1)>0)"},
  {"claim":"Q1 master case3: f=n^2 dominates n^(log_3 2)","code":"result=(2>log(2)/log(3))"}
]