playbooks

home / skills / a5c-ai / babysitter / recurrence-solver

recurrence-solver skill

/plugins/babysitter/skills/babysit/process/specializations/domains/science/computer-science/skills/recurrence-solver

This skill helps you solve recurrence relations from divide-and-conquer analysis using Master Theorem, substitutions, recursion trees, and generating functions.

npx playbooks add skill a5c-ai/babysitter --skill recurrence-solver

Review the files below or copy the command above to add this skill to your agents.

Files (1)
SKILL.md
1.1 KB
---
name: recurrence-solver
description: Solve recurrence relations using multiple methods including Master Theorem and generating functions
allowed-tools:
  - Bash
  - Read
  - Write
  - Edit
  - Glob
  - Grep
metadata:
  specialization: computer-science
  domain: science
  category: algorithm-analysis
  phase: 6
---

# Recurrence Solver

## Purpose

Provides expert guidance on solving recurrence relations arising from divide-and-conquer and recursive algorithm analysis.

## Capabilities

- Apply Master Theorem (all three cases)
- Substitution method with guess verification
- Recursion tree analysis with visualization
- Generating functions for complex recurrences
- Akra-Bazzi method for generalized recurrences
- Handle non-standard recurrence forms

## Usage Guidelines

1. **Recognition**: Identify recurrence structure and applicable methods
2. **Master Theorem**: Check and apply Master Theorem cases
3. **Substitution**: Formulate and verify guess for complex cases
4. **Tree Analysis**: Build recursion tree for intuition
5. **Verification**: Validate solutions with base cases

## Tools/Libraries

- SymPy
- Visualization libraries
- Symbolic algebra systems

Overview

This skill solves recurrence relations common in algorithm analysis using multiple formal methods. It produces step-by-step solutions, selects appropriate techniques (Master Theorem, substitution, recursion trees, generating functions, Akra–Bazzi) and verifies results against base cases. The output is practical and geared toward proving time complexity bounds and finding tight Theta expressions.

How this skill works

Given a recurrence, the skill first recognizes its structural form and suggests applicable solution strategies. It applies the Master Theorem when conditions match, performs substitution proofs for guessed bounds, constructs recursion trees to expose level contributions, and uses generating functions or Akra–Bazzi for nonstandard or continuous-parameter recurrences. Each solution includes verification of base cases and conditions that justify chosen steps.

When to use it

  • Analyzing divide-and-conquer algorithms where T(n)=a T(n/b)+f(n)
  • Proving upper and lower bounds when Master Theorem conditions fail or are ambiguous
  • Handling recurrences with nonpolynomial or irregular additive terms
  • Deriving exact or asymptotic forms using generating functions
  • Applying Akra–Bazzi to recurrences with nonuniform subproblem sizes

Best practices

  • Start by classifying the recurrence form before picking a method
  • Use Master Theorem only when regularity and polynomial comparisons hold
  • Verify guessed bounds via substitution and check base cases rigorously
  • Draw a recursion tree to build intuition and detect dominant levels
  • Switch to generating functions or Akra–Bazzi for irregular or mixed forms

Example use cases

  • Compute Theta bounds for classic mergesort-like recurrences with polynomial f(n)
  • Resolve recurrences with log factors or borderline cases where Master Theorem is inconclusive
  • Apply substitution to prove tight bounds for recurrences with additive lower-order terms
  • Use recursion trees to illustrate cost distribution across levels for teaching or documentation
  • Solve recurrences with varying subproblem sizes via the Akra–Bazzi framework

FAQ

Can the Master Theorem always be applied?

No. Master Theorem requires specific regularity and polynomial comparisons; use substitution, recursion trees, or Akra–Bazzi when conditions fail.

When should I use generating functions?

Use generating functions to obtain exact closed forms or to handle recurrences with nonstandard coefficients and convolution-like terms.