asymptotic analysis and recurrence relations notes

Anatomy of an Algorithmic Recurrence

Anatomy of an Algorithmic Recurrence An algorithmic recurrence relation expresses the running time of a recursive algorithm in terms of the running time on smaller inputs. 1. Base Case The time complexity for the smallest possible input size (e.g., T (1) = Θ (1)). 2. Recursive Step Time for input n, expressed as the sum of time to solve smaller subproblems and time to divide/combine. Merge Sort: T (n) = 2 T (n /2) + Θ (n)

The Substitution Method for Recurrences

The Substitution Method Guess the asymptotic bound, then verify using mathematical induction. Step 1 & 2: Guess T (n) \leq c n lo g n and verify base case. Step 3: Inductive step for T (n) = 2 T (⌊ n /2 ⌋) + n . T (n) \leq 2 (c \frac{n}{2} lo g \frac{n}{2}) + n T (n) \leq c n (lo g n - 1) + n T (n) \leq c n lo g n - (c - 1) n Since c \geq 1, - (c - 1) n \leq 0, proving T (n) = O (n lo g n) .

Visualizing Costs with the Recursion Tree Method

@keyframes pulseLevel { 0%, 100% { opacity: 0.6; transform: scale(0.98); } 50% { opacity: 1; transform: scale(1); } } .tree-node { animation: pulseLevel 2s infinite ease-in-out; } .tree-node:nth-child(1) { animation-delay: 0s; } .tree-node:nth-child(2) { animation-delay: 0.4s; } .tree-node:nth-child(3) { animation-delay: 0.8s; } Recursion Tree Method Visualize subproblem costs. Sum horizontally per level, then vertically across all levels. Level 0: c n^{2} \frac{3}{16} c n^{2} \frac{3}{16} c n^{2} \frac{3}{16} c n^{2} Level i : c n^{2} (\frac{3}{16})^{i} Total Cost (Geometric Series): T (n) \leq c n^{2} i = 0 \sum \infty (\frac{3}{16})^{i} = \frac{16}{13} c n^{2} ⟹ Θ (n^{2})

23 more cards in this chapter

Asymptotic Analysis and Recurrence Relations Notes for GATE CS

Asymptotic Analysis and Recurrence Relations notes for GATE CS: 26 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Anatomy of an Algorithmic Recurrence

An algorithmic recurrence relation expresses the running time of a recursive algorithm in terms of the running time on smaller inputs.

1. Base Case

The time complexity for the smallest possible input size (e.g., $T (1) = Θ (1)$ ).

2. Recursive Step

Time for input $n$ , expressed as the sum of time to solve smaller subproblems and time to divide/combine.

Merge Sort: $T (n) = 2 T (n /2) + Θ (n)$

The Substitution Method for Recurrences

The Substitution Method

Guess the asymptotic bound, then verify using mathematical induction.

Step 1 & 2: Guess

T (n) \leq c n lo g n

and verify base case.

Step 3: Inductive step for

T (n) = 2 T (⌊ n /2 ⌋) + n

    T(n)≤2(c2n​log2n​)+n
    T(n)≤cn(logn−1)+n
    T(n)≤cnlogn−(c−1)n
  

Since $c \geq 1$ , $- (c - 1) n \leq 0$ , proving $T (n) = O (n lo g n)$ .

Visualizing Costs with the Recursion Tree Method

Recursion Tree Method

Visualize subproblem costs. Sum horizontally per level, then vertically across all levels.

Level 0:

c n^{2}

\frac{3}{16} c n^{2}

\frac{3}{16} c n^{2}

\frac{3}{16} c n^{2}

Level

i

c n^{2} (\frac{3}{16})^{i}

Total Cost (Geometric Series):

$T (n) \leq c n^{2} i = 0 \sum \infty (\frac{3}{16})^{i} = \frac{16}{13} c n^{2} ⟹ Θ (n^{2})$

The Master Theorem for Divide and Conquer

The Master Theorem

For $T (n) = a T (n / b) + f (n)$ , compare $f (n)$ against critical function $n^{l o g_{b} a}$ .

Case 1: Leaves Dominate

$f (n) = O (n^{l o g_{b} a - ϵ})$

$T (n) = Θ (n^{l o g_{b} a})$

Case 2: Balanced

$f (n) = Θ (n^{l o g_{b} a} lo g^{k} n)$

$T (n) = Θ (n^{l o g_{b} a} lo g^{k + 1} n)$

Case 3: Root Dominates

$f (n) = Ω (n^{l o g_{b} a + ϵ})$ + regularity

$T (n) = Θ (f (n))$