First version from Cormen (not exhaustive) |  | Let a >= 1 and b > 1 be constants, let f(n) be an asymptotically positive function, and let T(n) be defined on the nonnegative integers by the recurrence T(n) = aT(n/b) + f(n), where we interpret n/b to mean either floor(n/b) or ceil(n/b). Then T(n) has the following asymptotic bounds: |  | (1). If f(n) = O(n^(logb_a-epsilon)) for some constant epsilon > 0, then T(n) = theta(n^(logb_a)). | (2). If f(n) = theta(n^(logb_a)), then T(n) = theta(n^(logb_a)lgn). | (3). If f(n) = Omega(n^(logb_a + epsilon)) for some constant epsilon > 0, and if af(n/b) <= cf(n) for some constant c < 1 and all sufficiently large n, then T(n) = theta(f(n)). |  | Abdul Bari version (exhaustive?) |  | Let a >= 1 and b > 1 be constants, let f(n) be an asymptotically positive function, and let T(n) be defined on the nonnegative integers by the recurrence T(n) = aT(n/b) + f(n), where we interpret n/b to mean either floor(n/b) or ceil(n/b). Then look at two values: logb_a, and k, in f(n) = O(n^(k)*log^p(n)). 3 cases: |  | Case 1: if logb_a > k, then theta(n^(logb_a)) | Case 2: if logb_a = k, then |   if p > -1, then theta(n^k * log^(p+1)n) |   if p = -1, then theta(n^k * loglogn) |   if p < -1, then theta(n^k) | Case 3: if logb_a < k |   if p >= 0, then theta(n^k * log^p(n)) |   if p < 0, then O(n^k) |