Master Theorem Calculator
Input
Enter values for : T(n) = aT(n/b) + O(n^d)
Result
Enter values and click "Calculate" to see results
How Master Theorem Works
The Master Theorem solves recurrences of the form:
Three Cases:
- Case 1: If log_b(a) < d, then
T(n) = O(n^d) - Case 2: If log_b(a) = d, then
T(n) = O(n^d log n) - Case 3: If log_b(a) > d, then
T(n) = O(n^log_b(a))
Example: Merge Sort has a=2, b=2, d=1, resulting in O(n log n)