🧮 Akra-Bazzi Recurrence Solver

A Python-based solver for analyzing and solving recurrence relations using the Akra-Bazzi method. This tool is perfect for students and professionals working with algorithm analysis, particularly in divide-and-conquer algorithms.

📋 Table of Contents

• Overview
• Features
• Requirements
• Installation
• Usage
• Akra-Bazzi Method Explained
• Examples
• Supported Functions
• Troubleshooting
• Contributing

Overview

The Akra-Bazzi method is a generalization of the Master Theorem used to solve recurrence relations of the form:

T(n) = Σ(i=1 to k) aᵢ · T(bᵢ · n) + g(n)

This solver automatically:

• ✅ Finds the critical exponent p
• ✅ Computes the required integral
• ✅ Provides the asymptotic solution Θ(·)
• ✅ Offers numerical verification

Features

• Interactive CLI: User-friendly command-line interface
• Multiple recurrence terms: Support for any number of recursive subproblems
• Common functions: Pre-defined templates for Θ(1), Θ(n), Θ(√n), Θ(n log n), etc.
• Custom functions: Define your own g(n) = n^k
• Symbolic computation: Automatic integral calculation
• Numerical verification: Test the solution with concrete values
• Educational output: Step-by-step solution display

Requirements

Python Version

• Python 3.7 or higher

Dependencies

numpy>=1.20.0
scipy>=1.7.0
sympy>=1.9

Installation

Step 1: Clone the Repository

git clone https://github.com/yourusername/akra-bazzi-solver.git
cd akra-bazzi-solver

Step 2: Install Dependencies

Option A: Using pip

pip install -r requirements.txt

Option B: Using conda

conda install numpy scipy sympy

Option C: Manual installation

pip install numpy scipy sympy

Step 3: Verify Installation

python akra_bazzi.py

Usage

Basic Usage

Run the script:

python akra_bazzi.py

Follow the interactive prompts:

1. Enter the number of recursive terms
2. For each term, specify:
   • Coefficient aᵢ
   • Fraction bᵢ
3. Choose or define g(n)
4. View the solution!

Quick Example

To solve T(n) = 2T(n/4) + √n:

Quanti termini ricorsivi ci sono? 1
Coefficiente a_1: 2
Frazione b_1: 0.25
Scegli il tipo di g(n): 4

Output:

SOLUZIONE FINALE:
T(n) = Θ(√n * log n)

Akra-Bazzi Method Explained

The Akra-Bazzi method solves recurrences in three steps:

Step 1: Find p

Solve the equation:

Σ aᵢ · bᵢᵖ = 1

Step 2: Compute the Integral

Calculate:

∫₁ⁿ g(u) / u^(p+1) du

Step 3: Apply the Formula

The solution is:

T(n) = Θ(nᵖ · (1 + ∫₁ⁿ g(u)/u^(p+1) du))

Examples

Example 1: Classic Merge Sort

Recurrence: T(n) = 2T(n/2) + n

Input:

Termini ricorsivi: 1
a_1: 2
b_1: 0.5
g(n): 2 (lineare)

Solution: T(n) = Θ(n log n)

---

Example 2: Binary Search

Recurrence: T(n) = T(n/2) + 1

Input:

Termini ricorsivi: 1
a_1: 1
b_1: 0.5
g(n): 1 (costante)

Solution: T(n) = Θ(log n)

---

Example 3: Karatsuba Multiplication

Recurrence: T(n) = 3T(n/2) + n

Input:

Termini ricorsivi: 1
a_1: 3
b_1: 0.5
g(n): 2 (lineare)

Solution: T(n) = Θ(n^1.585)

---

Example 4: Custom Recurrence

Recurrence: T(n) = 2T(n/4) + √n

Input:

Termini ricorsivi: 1
a_1: 2
b_1: 0.25
g(n): 4 (radice quadrata)

Solution: T(n) = Θ(√n log n)

---

Example 5: Multiple Terms

Recurrence: T(n) = T(n/3) + T(2n/3) + n

Input:

Termini ricorsivi: 2
a_1: 1, b_1: 0.333
a_2: 1, b_2: 0.667
g(n): 2 (lineare)

Solution: T(n) = Θ(n log n)

🔧 Supported Functions

Choice	Function	Notation	Use Case
1	Constant	Θ(1)	Binary search, simple operations
2	Linear	Θ(n)	Merge sort, quick sort
3	Quadratic	Θ(n²)	Nested loops
4	Square root	Θ(√n)	Specialized algorithms
5	Linearithmic	Θ(n log n)	Efficient sorting
6	Logarithmic	Θ(log n)	Binary search trees
7	Custom	Θ(n^k)	Any polynomial

Troubleshooting

ModuleNotFoundError: No module named 'X'

Solution:

pip install numpy scipy sympy

ImportError with scipy

Solution:

pip install --upgrade scipy

Numerical instability

If the solver can't find p, try:

• Verify your input values are correct
• Check that bᵢ values are fractions (0 < bᵢ < 1)
• Ensure aᵢ values are positive

Wrong results

• Make sure you're entering fractions correctly (e.g., 0.25 for n/4, not 4)
• Verify the recurrence is in the correct form

Contributing

Contributions are welcome! Here's how you can help:

1. Fork the repository
2. Create a feature branch (git checkout -b feature/AmazingFeature)
3. Commit your changes (git commit -m 'Add some AmazingFeature')
4. Push to the branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

Ideas for Contributions

• Add GUI interface
• Support for more complex g(n) functions
• Export results to LaTeX
• Graphical visualization of recursion tree
• Web interface
• More examples and test cases

Acknowledgments

• Based on the Akra-Bazzi theorem from "On the solution of linear recurrence equations" (1998)
• Inspired by algorithm analysis courses in computer science
• Thanks to the open-source community for numpy, scipy, and sympy

References

• Akra, M., & Bazzi, L. (1998). On the solution of linear recurrence equations. Computational Optimization and Applications, 10(2), 195-210.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.