Recurrence Relation and Master Theorem Calculator
Analyze divide-and-conquer recurrences of the form T(n)=aT(n/b)+Θ(n^k log^p n) using Master Theorem intuition.
Calculate
Model: T(n) = aT(n/b) + Θ(n^k log^p n)
What this calculator teaches
Recurrences describe recursive algorithm running time. The Master Theorem compares the work done at the leaves with the work done at each level.
This calculator gives a practical Big-O/Theta style classification for common divide-and-conquer recurrences.
Formula & Symbols
| Concept | Formula | Meaning |
|---|---|---|
| Recurrence | T(n)=aT(n/b)+f(n) | a subproblems, each of size n/b. |
| Critical exponent | c = log_b(a) | Compare f(n) with n^c. |
| Master comparison | f(n)=Θ(n^k log^p n) | k and p describe nonrecursive work. |
Step-by-Step Examples
- Merge sort has T(n)=2T(n/2)+n.
- a=2, b=2, so c=log₂2=1.
- f(n)=n, so k=1 and p=0.
- Binary search has T(n)=T(n/2)+1.
- a=1, b=2, c=0.
- f(n)=1, so k=0 and p=0.
Where students use this
Common Mistakes to Avoid
The split factor b describes smaller subproblems, so b > 1.
You must compare f(n) to n^{log_b a}.
Some recurrences need recursion trees, substitution, Akra-Bazzi, or other methods.
Frequently Asked Questions
Related Math Calculators
Formula Explorer connections
Interpretation: This relationship counts discrete structures, analyzes logic and sets, or describes algorithmic growth. Assumption: Define the sample space, recurrence, logical variables and counting constraints precisely. Avoid double counting and distinguish worst, average and best cases.