Recurrence Relations & Randomized Algorithms: Solving Recurrences & Probabilistic Design

TAKEAWAYS:

• Recurrence relations model divide-and-conquer algorithms (e.g., mergesort, binary search) and are solved via substitution, recursion trees, or the Master Theorem—each method has a distinct use case.
• Randomized algorithms (e.g., Miller-Rabin, quicksort with random pivots) trade determinism for efficiency, often achieving expected O(n log n) time where deterministic versions hit worst-case O(n²).
• The Master Theorem provides a shortcut for solving recurrences of the form $T(n)=aT(n/b)+f(n)$ by comparing $f(n)$ to $n^{{\log }_{b}a}$.
• Monte Carlo algorithms may return wrong answers with probability $<1$, while Las Vegas algorithms always give correct results but have random runtime.
• Recursion trees visually decompose recurrences into subproblems, revealing hidden patterns (e.g., geometric series in mergesort).
• Randomization in practice: Google’s PageRank uses probabilistic sampling, and Ncell’s call-routing algorithms rely on randomized load balancing.

1. Recurrence Relations: Modeling Divide-and-Conquer Algorithms

Recurrence relations express the runtime of recursive algorithms in terms of smaller inputs. For example, mergesort’s recurrence is: $$T(n)=2T(n/2)+O(n)$$ This means:

• Divide: Split the problem into 2 subproblems of size $n/2$.
• Conquer: Solve each subproblem recursively ($2T(n/2)$).
• Combine: Merge results in $O(n)$ time.

graph TD
    A["Divide: Split into 2 subproblems of size n/2"] --> B["Conquer: Solve recursively: 2T(n/2)"]
    A --> C["Combine: Merge in O(n) time"]
    B --> D["Base Case: T(1) = O(1)"]
    C --> E["Total Cost: O(n log n)"]

How to Solve Recurrences?

Three methods:

1. Substitution Method: Guess a solution (e.g., $T(n)=O(n\log n)$) and verify via induction.
2. Recursion Tree: Visualize the cost at each level of recursion.
3. Master Theorem: Direct formula for recurrences of the form $T(n)=aT(n/b)+f(n)$.

1.1 Substitution Method

Example: Solve $T(n)=2T(n/2)+n$ (mergesort). Guess: $T(n)=O(n\log n)$. Base Case: For $n=1$, $T(1)=c\le cn\log n$. Inductive Step: Assume $T(n/2)\le c(n/2)\log (n/2)$. Then: $$T(n)=2T(n/2)+n\le 2\cdot c(n/2)\log (n/2)+n=cn\log (n/2)+n=cn(\log n-1)+n.$$ We need $cn(\log n-1)+n\le cn\log n$: $$cn\log n-cn+n\le cn\log n⟹n\le cn⟹c\ge 1.$$ Thus, $T(n)=O(n\log n)$ holds for $c\ge 1$.

Visual Trace:

graph TD
    A["T(n) = 2T(n/2) + n"] --> B["T(n/2) = 2T(n/4) + n/2"]
    A --> C["T(n/2) = 2T(n/4) + n/2"]
    B --> D["T(n/4) = 2T(n/8) + n/4"]
    C --> E["T(n/4) = 2T(n/8) + n/4"]
    D --> F["T(n/8) = O(1)"]
    E --> G["T(n/8) = O(1)"]

Key Insight: The recursion tree for mergesort has $\log n$ levels, each costing $O(n)$.

1.2 Recursion Tree Method

Example: Solve $T(n)=T(n/4)+T(3n/4)+n$. Tree Structure:

Level 0: n
Level 1: n/4 + 3n/4 = n
Level 2: n/16 + 3n/16 + 3n/16 + 9n/16 = 2n
Level 3: 4n/64 + 9n/64 + 9n/64 + 27n/64 = 5n/16 + 27n/64 = (20n + 27n)/64 = 47n/64 ≈ 0.73n
...

Total Cost: Sum of a geometric series where each level’s cost decreases by a factor of $3/4$. Solution: $T(n)=O(n\log n)$.

Figure: Recursion Tree for $T(n)=T(n/4)+T(3n/4)+n$

levels = ["Level 0", "Level 1", "Level 2", "Level 3", "..."] costs = [n, n, 2n, 0.73n, "→ Geometric Series"]

The tree shows how costs accumulate across levels.

1.3 Master Theorem

For recurrences of the form $T(n)=aT(n/b)+f(n)$, compare $f(n)$ to $n^{{\log }_{b}a}$:

• Case 1: If $f(n)=O(n^{{\log }_{b}a-ϵ})$ for $ϵ>0$, then $T(n)=\Theta (n^{{\log }_{b}a})$.
• Case 2: If $f(n)=\Theta (n^{{\log }_{b}a}{\log }^{k}n)$, then $T(n)=\Theta (n^{{\log }_{b}a}{\log }^{k+1}n)$.
• Case 3: If $f(n)=\Omega (n^{{\log }_{b}a+ϵ})$ and $af(n/b)\le cf(n)$ for $c<1$, then $T(n)=\Theta (f(n))$.

Example: Solve $T(n)=4T(n/2)+n^2$.

• Here, $a=4$, $b=2$, so $n^{{\log }_{b}a}=n^2$.
• $f(n)=n^2=\Theta (n^{{\log }_{b}a})$.
• Case 2 applies: $T(n)=\Theta (n^2\log n)$.

Table: Master Theorem Cases

2. Randomized Algorithms: Probabilistic Efficiency

Randomized algorithms use randomness to achieve:

• Faster average-case performance (e.g., quicksort with random pivots).
• Simpler correctness proofs (e.g., Monte Carlo methods).
• Probabilistic guarantees (e.g., Las Vegas algorithms).

Types of Randomized Algorithms

2.1 Monte Carlo vs. Las Vegas

• Monte Carlo: May return incorrect results with small probability (e.g., "Is this number prime?" with 99% confidence).
• Las Vegas: Always correct but runtime is random (e.g., quicksort’s worst case is avoided by random pivots).

Example: Miller-Rabin Primality Test (Las Vegas). Input: Odd integer $n>2$, accuracy parameter $k$. Output: "Prime" or "Composite" with error probability $<4^{-k}$.

Algorithm Steps:

1. Write $n-1=2^s\cdot d$ where $d$ is odd.
2. Pick a random $a\in \{2,\dots ,n-2\}$.
3. Check:
   • If $a^d\equiv 1(\mathrm{mod}n)$ or $a^{2^{r}d}\equiv -1(\mathrm{mod}n)$ for some $0\le r<s$, then $n$ is probably prime.
   • Else, $n$ is definitely composite.
4. Repeat $k$ times. If all tests pass, $n$ is prime with probability $>1-4^{-k}$.

Code (Python-like Pseudocode):

def miller_rabin(n, k):
    if n <= 1: return False
    if n <= 3: return True
    if n % 2 == 0: return False
    # Write n-1 as 2^s * d
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    # Test k times
    for _ in range(k):
        a = rand(2, n-2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1: continue
        for __ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1: break
        else:
            return False
    return True

Trace for $n=561$ (Carmichael number, should fail):

Why Randomization?

• Deterministic primality tests (e.g., AKS) are slow ($O({\log }^{12}n)$).
• Miller-Rabin runs in $O(k{\log }^{3}n)$ and is used in Ncell’s SIM card authentication and eSewa’s transaction validation.

2.2 Randomized Quicksort

Problem: Quicksort’s worst case is $O(n^2)$ (e.g., already sorted array). Solution: Randomize the pivot selection.

Algorithm:

1. Pick a random pivot $p$ from the array.
2. Partition the array into $A<p$ and $A\ge p$.
3. Recurse on both partitions.

Expected Runtime: $O(n\log n)$ because the probability of worst-case splits is negligible.

Figure: Randomized Quicksort Partitioning

levels = ["Initial Array", "After 1st Partition", "After 2nd Partition", "..."] arrays = [ [3, 8, 7, 1, 9, 4, 5, 2, 6], # Random pivot = 5 ["<5: [3,1,4,2]", "≥5: [8,7,9,5,6]"], # Pivot moved to end ["<8: [3,1,4,2]", "≥8: [7,9,5,6]", "Pivot=8"] ]

Code:

import random
def randomized_quicksort(A, lo, hi):
    if lo >= hi: return
    p = random.randint(lo, hi)
    A[p], A[hi] = A[hi], A[p]  # Move pivot to end
    pivot = A[hi]
    i = lo
    for j in range(lo, hi):
        if A[j] <= pivot:
            A[i], A[j] = A[j], A[i]
            i += 1
    A[i], A[hi] = A[hi], A[i]  # Move pivot to correct position
    randomized_quicksort(A, lo, i-1)
    randomized_quicksort(A, i+1, hi)

Trace for $A=[3,8,7,1,9,4,5,2,6]$:

3. Real-World Applications

3.1 Recurrence Relations in Practice

• Google’s PageRank: The algorithm’s convergence is modeled by a recurrence relation involving the adjacency matrix of the web graph.
• Ncell’s Call Routing: The load on base stations is modeled recursively to optimize handoffs between towers.
• Daraz’s Order Processing: The time to process $n$ orders is $T(n)=T(n/2)+O(n)$ (divide orders into batches, process in parallel).

Example: NTC’s Network Latency Prediction Suppose NTC measures latency $T(n)$ for $n$ routers as: $$T(n)=2T(n/2)+n$$ Using the Master Theorem:

• $a=2$, $b=2$, $f(n)=n$.
• $n^{{\log }_{b}a}=n^1=n$.
• Case 2: $T(n)=\Theta (n\log n)$. Interpretation: Doubling routers increases latency by a logarithmic factor, guiding NTC’s infrastructure scaling.

3.2 Randomized Algorithms in Nepalese Tech

Example: Khalti’s Payment Queue Khalti processes $n$ payments in a queue. A deterministic FIFO queue could be exploited for denial-of-service (e.g., spamming small transactions). Instead, Khalti uses a randomized queue (like a priority queue with random priorities) to:

1. Assign each payment a random "priority" (e.g., timestamp + random salt).
2. Process payments in order of priority. Result: No single user can monopolize the queue, and the system remains $O(n\log n)$ on average.

4. Exam Tips

Recurrence Relations

• Master Theorem: Always check which case applies. If $f(n)$ is polynomial, compare exponents to $n^{{\log }_{b}a}$.
• Recursion Trees: Draw them for problems like $T(n)=T(n/3)+T(2n/3)+n$. The tree’s shape reveals the solution (e.g., $O(n\log n)$ for balanced splits).
• Substitution: Start with a guess based on the recursion tree. Verify via induction.

Randomized Algorithms

• Miller-Rabin: Know the steps for writing $n-1=2^{s}d$ and the loop for checking $a^{2^{r}d}\mathrm{mod}n$.
• Quicksort: The key insight is that random pivots make worst-case splits unlikely, not impossible.
• Monte Carlo vs. Las Vegas: Remember that Monte Carlo can lie, but Las Vegas never does—it just might take longer.

Common Pitfalls

• Assuming Case 1/2/3 without verification: Always compute $n^{{\log }_{b}a}$ and compare $f(n)$.
• Ignoring base cases: Recurrences like $T(n)=T(n-1)+1$ need $T(1)=1$ to solve to $O(n)$.
• Overlooking randomization: In quicksort, the pivot must be truly random (not just "first element") to avoid worst-case behavior.

Worked Exam Questions

Q1: Solve $T(n)=3T(n/4)+n$ using the Master Theorem. Solution:

• $a=3$, $b=4$, so $n^{{\log }_{b}a}=n^{{\log }_{4}3}\approx n^{0.792}$.
• $f(n)=n=\Omega (n^{0.792+ϵ})$ for $ϵ=0.208$.
• Case 3 applies: $T(n)=\Theta (n)$.

Q2: Explain why randomized quicksort has expected $O(n\log n)$ time. Solution:

• The probability of a pivot splitting the array into sizes $k$ and $n-k-1$ is $1/n$.
• The expected number of comparisons is: $$E[T(n)]=\frac{1}{n}\sum _{k=0}^{n-1}(k+(n-k-1)+E[T(k)]+E[T(n-k-1)])=n+\frac{2}{n}\sum _{k=0}^{n-1}E[T(k)].$$
• Solving this recurrence gives $E[T(n)]=O(n\log n)$.

Visual Summary

In the real world

• Google’s PageRank Algorithm: Uses randomized sampling to model the web as a Markov chain, where each page’s rank is computed by probabilistically following hyperlinks. This ensures efficient computation of global importance without exhaustive traversal.

• Ncell’s Call Routing: Employs randomized load balancing to distribute incoming calls across servers. By randomly selecting a server for each call, the system avoids worst-case congestion, achieving an expected O(n log n) efficiency in routing decisions.

• WhatsApp’s End-to-End Encryption: Relies on probabilistic primality testing (Miller-Rabin) to generate large prime numbers for key exchange. This ensures secure communication while maintaining computational efficiency.