Complexity Analysis

Q1. (3 marks) $f(n) = O(g(n))$ means there exist positive constants $c > 0$ and $n_0 > 0$ such that $0 \le f(n) \le c\,g(n) \quad \text{for all } n \ge n_0.$

• Statement of "exist constants $c, n_0$" — 1 mark
• Inequality $f(n) \le c\,g(n)$ — 1 mark
• "for all $n \ge n_0$" (asymptotic condition) — 1 mark

Why: Big-O is an asymptotic upper bound; it holds only beyond a threshold $n_0$ and up to a constant factor $c$.

Q2. (4 marks) $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$

• Constant/log/linear/linearithmic block correct — 2 marks
• Polynomial ($n^2, n^3$) before exponential/factorial — 1 mark
• Fully correct order — 1 mark

Why: Growth ranks as constant → logarithmic → polynomial (by degree) → exponential → factorial.

Q3. (4 marks)

• Best case: $O(1)$ — target is the first element checked. (1)
• Worst case: $O(n)$ — target is last or absent; all $n$ checked. (1.5)
• Average case: $O(n)$ — on average $\approx (n+1)/2$ comparisons if present, linear in $n$. (1.5)

Why: Best case counts the luckiest input; worst the hardest; average is the expected number of comparisons over inputs.

Q4. (4 marks)

• Auxiliary space: extra/temporary space used by an algorithm excluding the input itself. (1.5)
• Total space complexity: auxiliary space plus the space taken by the input. (1.5)
• Merge step using temp array of size $n$ ⇒ auxiliary space $= O(n)$. (1)

Why: Auxiliary isolates the algorithm's own overhead; total includes input storage.

Q5. (6 marks) — Master Theorem, $T(n)=aT(n/b)+f(n)$, compare $f(n)$ with $n^{\log_b a}$.

(a) $a=2,\,b=2 \Rightarrow n^{\log_2 2}=n$. $f(n)=n=\Theta(n)$ → Case 2. $T(n) = \Theta(n\log n). \quad \textbf{(2)}$

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

(c) $a=3,\,b=2 \Rightarrow n^{\log_2 3}\approx n^{1.585}$. $f(n)=n^2=\Omega(n^{\log_2 3+\epsilon})$ and regularity holds → Case 3. $T(n) = \Theta(n^2). \quad \textbf{(2)}$

Why: Compare driving function to $n^{\log_b a}$; smaller ⇒ leaves dominate (Case 1), equal ⇒ log factor (Case 2), larger ⇒ root dominates (Case 3).

Q6. (5 marks)

• $\Theta$: $f(n)=\Theta(g(n))$ iff $\exists\, c_1,c_2,n_0>0$ with $0\le c_1 g(n)\le f(n)\le c_2 g(n)$ for all $n\ge n_0$. (2)
• $\Omega$: $f(n)=\Omega(g(n))$ iff $\exists\, c,n_0>0$ with $0\le c\,g(n)\le f(n)$ for all $n\ge n_0$. (2)
• Relationship: $f(n)=\Theta(g(n))$ iff $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$. (1)

Why: $O$ = upper bound, $\Omega$ = lower bound, $\Theta$ = both (tight bound).

Q7. (5 marks) Guess $T(n) \le c\,n^2$. Unrolling: $T(n) = n + (n-1) + \dots + 1 = \frac{n(n+1)}{2}$. Substitution proof: assume $T(n-1) \le c(n-1)^2$. Then $T(n) = T(n-1) + n \le c(n-1)^2 + n = cn^2 - 2cn + c + n.$ This is $\le cn^2$ provided $-2cn + c + n \le 0$, i.e. for $c \ge 1$ and $n \ge 1$ (choose $c=1$: $-2n+1+n = 1-n \le 0$ for $n\ge1$). ✓ Hence $T(n) = O(n^2)$.

• Correct guess $cn^2$ — 1
• Inductive substitution — 2
• Showing residual $\le 0$ / valid $c$ — 1
• Conclusion — 1

Why: Substitution assumes the bound for smaller inputs and verifies the induction step holds with a fixed constant.

Q8. (5 marks) Aggregate method: Over $n$ appends, resizing occurs when size hits powers of $2$. Copy cost when growing to size $2^k$ is $2^k$ (moving elements). Total copy cost: $\sum_{k=0}^{\lfloor \log_2 n\rfloor} 2^k = 2^{\lfloor\log_2 n\rfloor+1}-1 < 2n.$ Plus $n$ simple insertions costing $n$. Total $= n + 2n = O(n)$. Amortized cost per append $= \dfrac{O(n)}{n} = O(1)$.

• Copy costs are powers of 2 — 1.5
• Geometric sum $< 2n$ — 1.5
• Total $O(n)$ — 1
• Amortized $O(1)$ — 1

Why: Rare expensive doublings sum to a geometric series bounded by $2n$; averaging over $n$ ops gives constant amortized cost.

Q9. (4 marks) Recursion tree for $T(n)=2T(n/2)+n$:

• Root does work $n$; splits into 2 subproblems of size $n/2$.
• Level $i$: $2^i$ nodes each of size $n/2^i$ → work $2^i \cdot \frac{n}{2^i} = n$ per level. (1.5)
• Number of levels: $\log_2 n + 1$ (until size 1). (1)
• Total work: $n \times (\log_2 n + 1) = \Theta(n\log n)$. (1.5)

Why: Each level contributes equal work $n$; multiplying by the tree height $\log_2 n$ gives $n\log n$.

[
  {"claim":"Master (a): 2T(n/2)+n gives n log n; work per level constant = n, levels = log2 n","code":"import sympy as sp\nn=sp.Symbol('n',positive=True)\n# n^(log_b a) with a=2,b=2\nexp=sp.log(2,2)\nresult=(exp==1)"},
  {"claim":"Master (b): 4T(n/2)+n, log_2 4 = 2, so Theta(n^2)","code":"import sympy as sp\nresult=(sp.log(4,2)==2)"},
  {"claim":"Master (c): 3T(n/2)+n^2, log_2 3 < 2 so f=n^2 dominates -> Theta(n^2)","code":"import sympy as sp\nresult=(sp.log(3,2) < 2)"},
  {"claim":"Q7 closed form: sum 1..n = n(n+1)/2 which is O(n^2)","code":"import sympy as sp\nn=sp.Symbol('n',positive=True,integer=True)\ns=sp.summation(sp.Symbol('k'),(sp.Symbol('k'),1,n))\nresult=(sp.simplify(s - n*(n+1)/2)==0)"},
  {"claim":"Q8 aggregate: sum of 2^k for k=0..m = 2^(m+1)-1 < 2*2^m","code":"import sympy as sp\nm=sp.Symbol('m',positive=True,integer=True)\ns=sp.summation(2**sp.Symbol('k'),(sp.Symbol('k'),0,m))\nresult=(sp.simplify(s-(2**(m+1)-1))==0)"}
]