recurrence                    log_b a   f(n)            case      T(n)
------------------------------------------------------------------------------------------------
T(n) = T(n/2) + 1             0         1               2         Theta(lg n)
T(n) = 9T(n/3) + n            2         n               1         Theta(n^2)
T(n) = 2T(n/2) + n            1         n               2         Theta(n lg n)
T(n) = 3T(n/4) + n lg n       0.792     n lg n          3         Theta(n lg n)   [regularity c = 0.750 < 1]
T(n) = 4T(n/2) + n^3          2         n^3             3         Theta(n^3)   [regularity c = 0.500 < 1]
T(n) = 2T(n/2) + n lg n       1         n lg n          gap 2-3   Theta(n lg^2 n) by other means
T(n) = 4T(n/2) + n            2         n               1         Theta(n^2)
T(n) = 4T(n/2) + n^2          2         n^2             2         Theta(n^2 lg n)
T(n) = 8T(n/2) + n^2          3         n^2             1         Theta(n^3)
T(n) = 7T(n/2) + n^2          2.807     n^2             1         Theta(n^2.807)
T(n) = 8T(n/2) + n^3          3         n^3             2         Theta(n^3 lg n)
T(n) = 2T(n/4) + sqrt(n)      0.500     n^0.500         2         Theta(n^0.500 lg n)
T(n) = 3T(n/3) + n/2          1         n               2         Theta(n lg n)
T(n) = 16T(n/4) + n^2         2         n^2             2         Theta(n^2 lg n)
T(n) = T(n/2) + n             0         n               3         Theta(n)   [regularity c = 0.500 < 1]
T(n) = 2T(n/2) + n/lg n       1         n/lg n          gap <2    not covered (answer Theta(n lg lg n))
T(n) = 5T(n/2) + n^2          2.322     n^2             1         Theta(n^2.322)
T(n) = T(2n/3) + 1            0         1               2         Theta(lg n)
