Master theorem solver (JavaScript)
In the study of complexity theory in computer science, analyzing the asymptotic run time of a recursive algorithm typically requires you to solve a recurrence relation. This JavaScript program automatically solves your given recurrence relation by applying the versatile master theorem (a.k.a. master method). However, it only supports functions that are polynomial or polylogarithmic. (The source code is available for viewing.)
Program
Examples
| Name & demo | \(a\) | \(b\) | \(k\) |
|---|---|---|---|
| Binary search | 1 | 2 | 0 |
| Binary tree traversal | 2 | 2 | 0 |
| Merge sort | 2 | 2 | 1 |
| Toom-4 multiplication | 7 | 4 | 1 |
| Toom-3 multiplication | 5 | 3 | 1 |
| Karatsuba multiplication | 3 | 2 | 1 |
| Stooge sort | 3 | 1.5 | 1 |
| Strassen matrix multiplication | 7 | 2 | 2 |
Click on an example to run the numbers in the calculator.