Asymptotics & Notation

• Order: \(f\in O(g)\iff \exists c,n_0: \forall n\ge n_0,\ 0\le f(n)\le c\,g(n)\).
• Lower: \(f\in \Omega(g)\iff \exists c,n_0: f(n)\ge c\,g(n)\) (for large \(n\)).
• Tight: \(f\in \Theta(g)\iff f\in O(g)\land f\in \Omega(g)\).
• Little‑o: \(f\in o(g)\iff \forall c>0,\exists n_0: f(n)\le c\,g(n)\) (i.e., \(f/g\to 0\)).
• Little‑ω: \(f\in \omega(g)\iff g\in o(f)\).
• Poly‑bounded: \(f(n)\) polynomially bounded \(\iff \exists k: f(n)\in O(n^k)\).
• \(\log_a n = \dfrac{\log_b n}{\log_b a}\), \(\sum_{i=0}^{k-1} r^i=\dfrac{1-r^k}{1-r}\).
• Stirling: \(n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\), so \(\log n!\sim n\log n - n\).

Amortized (Aggregate/Accounting/Potential)

• Binary counter (flip LSBs on INCREMENT): total bit flips over \(n\) increments \(\le 2n\) ⇒ \(O(1)\) amortized.
• Stack with MULTIPOP: each element popped once ⇒ any \(n\) ops cost \(O(n)\).
• Dynamic array doubling: total copies over \(n\) appends \(\le 2n\) ⇒ \(O(1)\) amortized append.

Divide & Conquer / Master Method

• Form: \(T(n)=a\,T(n/b)+f(n)\), \(a\ge1,b>1\).
• Let \(n^{\log_b a}\) be the critical term.
  • Case 1: if \(f(n)=O(n^{\log_b a-\varepsilon})\) ⇒ \(T(n)=\Theta(n^{\log_b a})\).
  • Case 2: if \(f(n)=\Theta(n^{\log_b a}\log^k n)\) ⇒ \(T(n)=\Theta(n^{\log_b a}\log^{k+1} n)\).
  • Case 3: if \(f(n)=\Omega(n^{\log_b a+\varepsilon})\) and regularity \(a\,f(n/b)\le c f(n)\) (\(c<1\)) ⇒ \(T(n)=\Theta(f(n))\).
• Common recurrences:
  • Merge sort: \(T(n)=2T(n/2)+\Theta(n)\Rightarrow \Theta(n\log n)\).
  • Binary search: \(T(n)=T(n/2)+\Theta(1)\Rightarrow \Theta(\log n)\).
  • Karatsuba: \(T(n)=3T(n/2)+\Theta(n)\Rightarrow \Theta(n^{\log_2 3})\).
  • Strassen: \(T(n)=7T(n/2)+\Theta(n^2)\Rightarrow \Theta(n^{\log_2 7})\).

Greedy Algorithms

• Exchange argument: transform any optimal to greedy solution without loss.
• Matroid greedy: greedy by weight is optimal on matroids.
• Interval scheduling (1 room): select by earliest finish time ⇒ max compatible set.
• Min rooms (Lecture Hall): sort by start time; use min‑heap of end times; rooms = max overlap.
• Scheduling to minimize max lateness: order by nondecreasing due dates (\(d_i\)).
• Fractional knapsack: take items by value/weight ratio ⇒ optimal; \(O(n\log n)\) (or \(O(n)\) with selection).
• Prim/Kruskal (MST): cut/property ⇒ greedy optimality.

Dynamic Programming (DP)

• LCS: strings \(X[1..m],Y[1..n]\). \[ \text{dp}[i,j]=\begin{cases} 0 & i=0\text{ or }j=0\\ \text{dp}[i-1,j-1]+1 & X_i=Y_j\\ \max(\text{dp}[i-1,j],\text{dp}[i,j-1]) & \text{else} \end{cases} \] Time/space \(O(mn)\); space reduce to \(O(\min(m,n))\) for length.
• 0/1 Knapsack: capacity \(W\), items \((v_i,w_i)\). \[ \text{dp}[i,w]=\max\big(\text{dp}[i-1,w],\ \text{dp}[i-1,w-w_i]+v_i\big) \] Time \(O(nW)\), space \(O(W)\). FPTAS via scaling.
• Matrix chain: \(A_1..A_n\) dims \(p_{i-1}\times p_i\). \[ \text{dp}[i,i]=0,\ \text{dp}[i,j]=\min_{i\le k
• Edit distance: \(\text{dp}[i,0]=i,\ \text{dp}[0,j]=j\), \(\text{dp}[i,j]=\min\{\text{dp}[i-1,j]+1,\text{dp}[i,j-1]+1,\text{dp}[i-1,j-1]+\![X_i\ne Y_j]\}\).

Medians & Order Statistics

• Quickselect (randomized): expected \(O(n)\). Recurrence \(T(n)=T(\alpha n)+O(n)\) in expectation.
• BFPRT (median‑of‑medians): \(T(n)\le T(\lceil n/5\rceil)+T(7n/10)+O(n)=O(n)\).
• Median: \(k=\lceil n/2\rceil\) via selection in linear time.

Sorting: Bounds & Algorithms

• Comparison lower bound: decision tree with \(\ge n!\) leaves ⇒ height \(\ge \log_2(n!)=\Theta(n\log n)\).
• Quicksort:
  • Recurrence (avg.): \(T(n)=T(\alpha n)+T((1-\alpha)n)+\Theta(n)\Rightarrow \Theta(n\log n)\).
  • Worst: \(T(n)=T(n-1)+\Theta(n)=\Theta(n^2)\). Randomized pivot ⇒ expected \(\Theta(n\log n)\).
• Mergesort: stable, \(\Theta(n\log n)\), extra space \(O(n)\).
• Non‑comparison sorts: Counting/Radix/Bucket: linear time under assumptions.

Recurrence Examples (Grab‑bag)

• \(T(n)=T(n-1)+n \Rightarrow \Theta(n^2)\), \(T(n)=T(n-1)+n^4 \Rightarrow \Theta(n^5)\).
• \(T(n)=a\,T(n/b)+n^k\): compare \(k\) with \(\log_b a\) (master method).
• \(T(n)=T(\alpha n)+T((1-\alpha)n)+\Theta(n) \Rightarrow \Theta(n\log n)\) (balanced split).

Useful Identities & Tips

• \(\sum_{i=1}^{n}\log i=\log n! \sim n\log n-n\).
• \(\sum_{i=0}^{\lfloor \log_b n\rfloor} a^i = \Theta(a^{\log_b n})=\Theta(n^{\log_b a})\) if \(a>1\).
• When proving greedy optimality: use exchange or cut/cycle properties.
• DP pattern: define state, recurrence, base cases, order, and reconstruction.
• Amortized proofs: aggregate (sum), accounting (credits), potential (\(\Phi\) such that amortized \(=\) actual+\(\Delta\Phi\)).