Coding interleaved practice

1. (Subtopic 3.1.1 — Big-O formal definition) We need $c, n_0 > 0$ such that $3n^2 + 100n + 7 \le c\,n^2$ for all $n \ge n_0$. For $n \ge 1$: $100n \le 100n^2$ and $7 \le 7n^2$, so $3n^2 + 100n + 7 \le (3+100+7)n^2 = 110 n^2$. Thus $c = 110,\ n_0 = 1$ works. Statement true: $3n^2+100n+7 = O(n^2)$. (Tighter: choose $c=4$, then $100n+7 \le n^2$ needs $n \ge 101$, so $n_0=101$, $c=4$.) Why this method: "Prove using formal definition" ⇒ must exhibit witnesses $c, n_0$, not just assert dominant term.

2. (Subtopic 3.1.7 — Master theorem) $a=2,\ b=2,\ f(n)=n$. Compute $n^{\log_b a} = n^{\log_2 2} = n^1 = n$. Since $f(n) = \Theta(n^{\log_b a}) = \Theta(n)$, Case 2 applies. $T(n) = \Theta(n^{\log_b a}\log n) = \boxed{\Theta(n\log n)}$. Why: Recurrence is divide-by-$b$ form $aT(n/b)+f(n)$ ⇒ Master theorem is the direct tool; comparing $f$ to $n^{\log_b a}$ selects the case.

3. (Subtopic 3.2.1 / 3.1.5 — amortized append, aggregate method) Cheap appends cost 1 each. Resizes happen at sizes $1,2,4,\dots,2^k \le n$, copying $1+2+4+\cdots+2^k < 2n$ elements total. Total work $= n$ (appends) $+ <2n$ (copies) $< 3n = O(n)$. Amortized cost per append $= O(n)/n = \boxed{O(1)}$. Why: "Total cost of $n$ operations" ⇒ aggregate method: sum everything, divide by $n$.

4. (Subtopic 3.2.2 / 3.2.3 — linked list insert) With only the head, reaching the middle requires traversing $\sim n/2$ nodes: worst case $\Theta(n)$. Once at the target node, the pointer splice is $O(1)$. In a doubly linked list, if you already hold the node, you have both prev and next pointers, so insertion/deletion is $O(1)$ with no traversal — the back-pointer removes the need to search for the predecessor. Why: Tests distinguishing access cost from splice cost; the DLL back-pointer is the discriminating feature.

5. (Subtopic 3.1.9 — recursion tree) Root cost $n^2$. At depth $i$: $3^i$ subproblems each of size $n/4^i$, cost per node $(n/4^i)^2 = n^2/16^i$. Level cost $= 3^i \cdot n^2/16^i = (3/16)^i n^2$. Sum over levels: $n^2\sum_{i\ge0}(3/16)^i = n^2 \cdot \frac{1}{1-3/16} = \frac{16}{13}n^2$. Total $= \boxed{\Theta(n^2)}$ (root-dominated geometric series). Matches Master Case 3. Why: Recursion tree explicitly shows the geometric decay per level — chosen when you want to see which level dominates.

6. (Subtopic 3.3.3 — chaining, load factor) Under simple uniform hashing, expected chain length $= \alpha = n/m$. Expected successful-search time $= \Theta(1 + \alpha)$. If $\alpha$ stays $O(1)$ (via resizing), search is $\Theta(1)$. Without resizing, $\alpha = n/m$ grows linearly, degrading search to $\Theta(n)$. Why: Chaining performance is governed by load factor $\alpha$; distinguishes it from open addressing where $\alpha < 1$ strictly.

7. (Subtopic 3.3.4 — open addressing / linear probing)

• Best case: $O(1)$ — target slot empty on first probe.
• Worst case: $O(n)$ — long probe run wraps most of the table.
• Average case: $\approx \tfrac{1}{2}\left(1+\frac{1}{1-\alpha}\right)$ probes for insertion, i.e. $O\!\left(\frac{1}{1-\alpha}\right)$ — blows up as $\alpha \to 1$. Degrading phenomenon: primary clustering — occupied runs grow and merge. Why: Requires the three-case framing plus naming linear probing's specific failure mode (contrast with double hashing which avoids primary clustering).

8. (Subtopic 3.1.8 — substitution method) Guess $T(n) \le c\,n\log n$. Inductive step (assume for $n/2$): $T(n) = 2T(n/2) + n \le 2\left(c\frac{n}{2}\log\frac{n}{2}\right) + n = c n(\log n - 1) + n = c n\log n - cn + n$. This is $\le c n\log n$ provided $-cn + n \le 0$, i.e. $c \ge 1$. Base case $n=2$: choose $c$ large enough to cover $T(2)$. Hence $T(n)=O(n\log n)$. ∎ Why: "Prove is $O(\cdot)$" with a known guess ⇒ substitution (guess + induction), not Master theorem which only gives the bound without the proof.

9. (Subtopic 3.3.5 — tombstones) Blanking a slot breaks probe sequences: a later lookup for a key whose probe path passed through the blanked slot would stop early and wrongly report "not found." Fix: mark the slot with a tombstone (DELETED sentinel) — probing continues past it during search, but insertion may reuse it. Downside: tombstones accumulate, keeping effective load factor high and lengthening probe sequences; periodic rehashing is needed to purge them. Why: Tests understanding that open addressing correctness depends on unbroken probe chains — impossible issue in chaining.

10. (Subtopic 3.1.4 — auxiliary vs total space)

• Auxiliary space = extra memory beyond the input. Top-down merge sort allocates temporary merge buffers totaling $\Theta(n)$, plus recursion stack $\Theta(\log n)$ ⇒ auxiliary $= \Theta(n)$.
• Total space = input + auxiliary $= \Theta(n) + \Theta(n) = \Theta(n)$. (For contrast, an in-place algorithm like heapsort has auxiliary $\Theta(1)$ but still total $\Theta(n)$.) Why: Forces separating "extra used" from "everything used" — the buffer $\Theta(n)$ is auxiliary, distinct from the input $n$.

[
  {
    "claim": "3n^2+100n+7 <= 110 n^2 for all n>=1 (Problem 1 witnesses)",
    "code": "import sympy as sp\nn=sp.symbols('n',positive=True)\n# check minimum of 110*n**2 - (3*n**2+100*n+7) is >=0 for n>=1\nexpr=110*n**2-(3*n**2+100*n+7)\nval_at_1=expr.subs(n,1)\nderiv_positive=sp.simplify(sp.diff(expr,n)).subs(n,1)>0\nresult = bool(val_at_1>=0 and deriv_positive)"
  },
  {
    "claim": "Master theorem: T(n)=2T(n/2)+n gives Theta(n log n) (Problem 2)",
    "code": "import sympy as sp\na,b=2,2\nlog_ba=sp.log(a,b)\n# n^log_ba == n^1, f=n, so case 2 -> n^1 * log n\ncase2 = sp.simplify(log_ba-1)==0\nresult = bool(case2)"
  },
  {
    "claim": "Recursion tree sum for T(n)=3T(n/4)+n^2 equals (16/13) n^2 (Problem 5)",
    "code": "import sympy as sp\ni=sp.symbols('i',nonnegative=True)\nn=sp.symbols('n',positive=True)\nS=sp.summation((sp.Rational(3,16))**i,(i,0,sp.oo))*n**2\nresult = bool(sp.simplify(S-sp.Rational(16,13)*n**2)==0)"
  }
]