Master Theorem Calculator
The master theorem compares f(n) with n^(log_b a): T(n) = 8T(n/2) + n² is Θ(n^3) because n³ dominates n².
Θ(n^3)
- log_b a
- 3
- Recurrence
- T(n) = 8T(n/2) + Θ(n^2)
Step-by-step solution
- Compare f(n) = Θ(n^2) with n^(log_b a) = n^3
- Case 1: k = 2 < log_b a = 3
- T(n) = Θ(n^3)
Master Theorem Formula
T(n) = aT(n/b) + Θ(nᵏ logᵖ n)
compare k with log_b a
Worked Example
T(n) = 8T(n/2) + n²:
- Compare f(n) = Θ(n^2) with n^(log_b a) = n^3
- Case 1: k = 2 < log_b a = 3
- T(n) = Θ(n^3)
Recurrence: T(n) = 8T(n/2) + Θ(n^2)
GATE tip
Binary search is T(n) = T(n/2) + 1 (a = 1, b = 2, k = 0) → Θ(log n); Strassen is 7T(n/2) + n² → Θ(n^2.807).
More Computer Networks and Algorithms Calculators
-
Subnet Calculator
network = IP AND mask, broadcast = network OR wildcard
hosts = 2^(32 − prefix) − 2
Example: 192.168.10.77/26: Network address = 192.168.10.64/26.
-
CRC Calculator
frame = data · 2ʳ + (data · 2ʳ mod G)
modulo-2 (XOR) division; r = degree of G
Example: Data 1101011111 with generator x⁴ + x + 1 (10011): Transmitted frame = 11010111110010.
-
Hamming Code Calculator
2ʳ ≥ m + r + 1
parity bit p checks positions with bit p set; syndrome = error position
Example: The data bits 1011: Hamming code word = 0110011.
-
Sliding Window Efficiency Calculator
η = N ÷ (1 + 2a), a = Tp ÷ Tt
GBN sequence bits ⌈log₂(N + 1)⌉, SR ⌈log₂ 2N⌉
Example: A 10 Mbps link, 1000-byte frames, 20 ms one-way delay and a window of 7 (Go-Back-N): Efficiency = 13.7254902 %.
Frequently asked questions
What is the recurrence for merge sort?
T(n) = 2T(n/2) + n, which is case 2 of the master theorem and gives Θ(n log n).
When does the master theorem not apply?
When subproblems have unequal sizes, a is not constant, or f(n) is not polynomially comparable, e.g. T(n) = T(n − 1) + n.
Sources
Last reviewed: . Factors are stored exactly and computed with 50-digit decimal arithmetic. See how we verify conversion factors.
Cite this page
APA
Scientific Converters. (2026, October 15). Master Theorem Calculator. Retrieved October 25, 2026, from https://scientificconverters.com/calculators/master-theorem-calculator/
IEEE
Scientific Converters, "Master Theorem Calculator," scientificconverters.com. Accessed: Oct. 25, 2026. [Online]. Available: https://scientificconverters.com/calculators/master-theorem-calculator/