3 includes technical condition on lower integral bound and updates examples accordingly.

The Akra-Bazzi method

The Akra-Bazzi method gives asymptotics for recurrences of the form: $$T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for x \ge x_0}$$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $$h_i(x)$$ can cater for divisions that don't come out exact, for example. The conditions for applicability are:

• There are enough base cases to get the recurrence going
• The $$a_i$$ and $$b_i$$ are all constants
• For all $$i$$, $$a_i > 0$$
• For all $$i$$, $$0 < b_i < 1$$
• $$\lvert g(x) \rvert = O(x^c)$$ for some constant $$c$$ as $$x \rightarrow \infty$$
• For all $$i$$, $$\lvert h_i(x) \rvert = O(x / (\log x)^2)$$
• $$x_0$$ is a constant

Note that $$\lfloor b_i x \rfloor = b_i x - \{b_i x\}$$, and as the sawtooth function $$\{ u \} = u - \lfloor u \rfloor$$ is always between 0 and 1, replacing $$\lfloor b_i x \rfloor$$ (or $$\lceil b_i x \rceil$$ as appropiate) satisfies the conditions on the $$h_i$$.

Find $$p$$ such that: $$\sum_{1 \le i \le k} a_i b_i^p = 1$$ Then the asymptotic behaviour of $$T(x)$$ as $$x \rightarrow \infty$$ is given by: $$T(x) = \Theta \left( x^p \left( 1 + \int _1^x \frac{g(u)}{u^{p + 1}} du \right) \right)$$$$T(x) = \Theta \left( x^p \left( 1 + \int_{x_1}^x \frac{g(u)}{u^{p + 1}} du \right) \right)$$ with $$x_1$$ "large enough", i.e. there is $$k_1>0$$ so that $$g(x/2) \geq k_1g(x) \tag{2}$$ for all $$x>x_1$$.

ExamplesExample A

As an example, take the recursion for $$n \ge 5$$, where $$T(0) = T(1) = T(2) = T(3) = T(4) = 17$$: $$T(n) = 9 T(\lfloor n / 5 \rfloor) + T(\lceil 4 n / 5 \rceil) + 3 n \log n$$ The conditions are satisfied, we need $$p$$: $$9 \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1$$ As luck would have it, $$p = 2$$. Thus we have: $$T(n) = \Theta \left( n^2 \left(1 + \int_1^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$$$T(n) = \Theta \left( n^2 \left(1 + \int_3^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$

since with $$k_1 \leq \frac{1}{2}\left(1 - \frac{\log 2}{\log 3}\right)$$ we fulfill $$(2)$$ for all $$x\geq 3$$. Note that because the integral converges even if we use other constants, such as $$1$$, as lower bound, it is legal to use those as well; the difference vanishes in $$\Theta$$.

Example B

Another example is the following for $$n \ge 2$$: $$T(n) = 4 T(n / 2) + n^2 / \lg n$$ We have $$g(n) = n^2 / \ln n = O(n^2)$$, check. We have that there is a single $$a_1 = 4$$, $$b_1 = 1 / 2$$, which checks out. Assuming that the $$n / 2$$ is really $$\lfloor n / 2 \rfloor$$ and/or $$\lceil n / 2 \rceil$$, the implied $$h_i(n)$$ also check out. So we need: $$a_1 b_1^p = 4 \cdot (1 / 2)^p = 1$$ Thus $$p = 2$$, and: $$T(n) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{u^2 du}{u^3 \ln u} \right) \right) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{du}{u \ln u} \right) \right) = \Theta(n^2 \ln \ln n)$$ (The integralWe apply a similar trick as given with lower limit 1 diverges, butabove to the lower limit should really bebound of the integral, only that we use $$n$$ for which the recurrence starts being valid; check$$2$$ because the original paperintegral does not converge for $$1$$.)

(The help of maxima with the algebra is gratefully acknowledged)

The Akra-Bazzi method

The Akra-Bazzi method gives asymptotics for recurrences of the form: $$T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for x \ge x_0}$$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $$h_i(x)$$ can cater for divisions that don't come out exact, for example. The conditions for applicability are:

• There are enough base cases to get the recurrence going
• The $$a_i$$ and $$b_i$$ are all constants
• For all $$i$$, $$a_i > 0$$
• For all $$i$$, $$0 < b_i < 1$$
• $$\lvert g(x) \rvert = O(x^c)$$ for some constant $$c$$ as $$x \rightarrow \infty$$
• For all $$i$$, $$\lvert h_i(x) \rvert = O(x / (\log x)^2)$$
• $$x_0$$ is a constant

Note that $$\lfloor b_i x \rfloor = b_i x - \{b_i x\}$$, and as the sawtooth function $$\{ u \} = u - \lfloor u \rfloor$$ is always between 0 and 1, replacing $$\lfloor b_i x \rfloor$$ (or $$\lceil b_i x \rceil$$ as appropiate) satisfies the conditions on the $$h_i$$.

Find $$p$$ such that: $$\sum_{1 \le i \le k} a_i b_i^p = 1$$ Then the asymptotic behaviour of $$T(x)$$ as $$x \rightarrow \infty$$ is given by: $$T(x) = \Theta \left( x^p \left( 1 + \int _1^x \frac{g(u)}{u^{p + 1}} du \right) \right)$$

Examples

As an example, take the recursion for $$n \ge 5$$, where $$T(0) = T(1) = T(2) = T(3) = T(4) = 17$$: $$T(n) = 9 T(\lfloor n / 5 \rfloor) + T(\lceil 4 n / 5 \rceil) + 3 n \log n$$ The conditions are satisfied, we need $$p$$: $$9 \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1$$ As luck would have it, $$p = 2$$. Thus we have: $$T(n) = \Theta \left( n^2 \left(1 + \int_1^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$

Another example is the following for $$n \ge 2$$: $$T(n) = 4 T(n / 2) + n^2 / \lg n$$ We have $$g(n) = n^2 / \ln n = O(n^2)$$, check. We have that there is a single $$a_1 = 4$$, $$b_1 = 1 / 2$$, which checks out. Assuming that the $$n / 2$$ is really $$\lfloor n / 2 \rfloor$$ and/or $$\lceil n / 2 \rceil$$, the implied $$h_i(n)$$ also check out. So we need: $$a_1 b_1^p = 4 \cdot (1 / 2)^p = 1$$ Thus $$p = 2$$, and: $$T(n) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{u^2 du}{u^3 \ln u} \right) \right) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{du}{u \ln u} \right) \right) = \Theta(n^2 \ln \ln n)$$ (The integral as given with lower limit 1 diverges, but the lower limit should really be the $$n$$ for which the recurrence starts being valid; check the original paper.)

(The help of maxima with the algebra is gratefully acknowledged)

The Akra-Bazzi method

The Akra-Bazzi method gives asymptotics for recurrences of the form: $$T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for x \ge x_0}$$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $$h_i(x)$$ can cater for divisions that don't come out exact, for example. The conditions for applicability are:

• There are enough base cases to get the recurrence going
• The $$a_i$$ and $$b_i$$ are all constants
• For all $$i$$, $$a_i > 0$$
• For all $$i$$, $$0 < b_i < 1$$
• $$\lvert g(x) \rvert = O(x^c)$$ for some constant $$c$$ as $$x \rightarrow \infty$$
• For all $$i$$, $$\lvert h_i(x) \rvert = O(x / (\log x)^2)$$
• $$x_0$$ is a constant

Note that $$\lfloor b_i x \rfloor = b_i x - \{b_i x\}$$, and as the sawtooth function $$\{ u \} = u - \lfloor u \rfloor$$ is always between 0 and 1, replacing $$\lfloor b_i x \rfloor$$ (or $$\lceil b_i x \rceil$$ as appropiate) satisfies the conditions on the $$h_i$$.

Find $$p$$ such that: $$\sum_{1 \le i \le k} a_i b_i^p = 1$$ Then the asymptotic behaviour of $$T(x)$$ as $$x \rightarrow \infty$$ is given by: $$T(x) = \Theta \left( x^p \left( 1 + \int_{x_1}^x \frac{g(u)}{u^{p + 1}} du \right) \right)$$ with $$x_1$$ "large enough", i.e. there is $$k_1>0$$ so that $$g(x/2) \geq k_1g(x) \tag{2}$$ for all $$x>x_1$$.

Example A

As an example, take the recursion for $$n \ge 5$$, where $$T(0) = T(1) = T(2) = T(3) = T(4) = 17$$: $$T(n) = 9 T(\lfloor n / 5 \rfloor) + T(\lceil 4 n / 5 \rceil) + 3 n \log n$$ The conditions are satisfied, we need $$p$$: $$9 \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1$$ As luck would have it, $$p = 2$$. Thus we have: $$T(n) = \Theta \left( n^2 \left(1 + \int_3^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$

since with $$k_1 \leq \frac{1}{2}\left(1 - \frac{\log 2}{\log 3}\right)$$ we fulfill $$(2)$$ for all $$x\geq 3$$. Note that because the integral converges even if we use other constants, such as $$1$$, as lower bound, it is legal to use those as well; the difference vanishes in $$\Theta$$.

Example B

Another example is the following for $$n \ge 2$$: $$T(n) = 4 T(n / 2) + n^2 / \lg n$$ We have $$g(n) = n^2 / \ln n = O(n^2)$$, check. We have that there is a single $$a_1 = 4$$, $$b_1 = 1 / 2$$, which checks out. Assuming that the $$n / 2$$ is really $$\lfloor n / 2 \rfloor$$ and/or $$\lceil n / 2 \rceil$$, the implied $$h_i(n)$$ also check out. So we need: $$a_1 b_1^p = 4 \cdot (1 / 2)^p = 1$$ Thus $$p = 2$$, and: $$T(n) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{u^2 du}{u^3 \ln u} \right) \right) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{du}{u \ln u} \right) \right) = \Theta(n^2 \ln \ln n)$$ We apply a similar trick as above to the lower bound of the integral, only that we use $$2$$ because the integral does not converge for $$1$$.

(The help of maxima with the algebra is gratefully acknowledged)

2 Add example from http://cs.stackexchange.com/q/10977/6447, typo

The Akra-Bazzi method

The Akra-Bazzi method gives asymptotics for recurrences of the form: $$T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for x \ge x_0}$$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $$h_i(x)$$ can cater for divisions that don't come out exact, for example. The conditions for applicability are:

• There are enough base cases to get the recurrence going
• The $$a_i$$ and $$b_i$$ are all constants
• For all $$i$$, $$a_i > 0$$
• For all $$i$$, $$0 < b_i < 1$$
• $$\lvert g(x) \rvert = O(x^c)$$ for some constant $$c$$ as $$x \rightarrow \infty$$
• For all $$i$$, $$\lvert h_i(x) \rvert = O(x / (\log x)^2)$$
• $$x_0$$ is a constant

Note that $$\lfloor b_i x \rfloor = b_i x - \{b_i x\}$$, and as the sawtooth function $$\{ u \} = u - \lfloor u \rfloor$$ is always between 0 and 1, replacing $$\lfloor b_i x \rfloor$$ (or $$\lceil b_i x \rceil$$ as appropiate) satisfies the conditions on the $$h_i$$.

Find $$p$$ such that: $$\sum_{1 \le i \le k} a_i b_i^p = 1$$ Then the asymptotic behaviour of $$T(x)$$ as $$x \rightarrow \infty$$ is given by: $$T(x) = \Theta \left( x^p \left( 1 + \int _1^x \frac{g(u)}{u^{p + 1}} du \right) \right)$$

ExampleExamples

As an example, take the recursion for $$n \ge 5$$, where $$T(0) = T(1) = T(2) = T(3) = T(4) = 17$$: $$T(n) = 9 T(\lfloor n / 5 \rfloor) + T(\lceil 4 n / 5 \rceil) + 3 n \log n$$ The conditions are satisfied, we need $$p$$: $$9 \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1$$ As luck would have it, $$p = 2$$. Thus we have: $$T(n) = \Theta \left( n^2 \left(1 + \int_1^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$$$T(n) = \Theta \left( n^2 \left(1 + \int_1^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$

Another example is the following for $$n \ge 2$$: $$T(n) = 4 T(n / 2) + n^2 / \lg n$$ We have $$g(n) = n^2 / \ln n = O(n^2)$$, check. We have that there is a single $$a_1 = 4$$, $$b_1 = 1 / 2$$, which checks out. Assuming that the $$n / 2$$ is really $$\lfloor n / 2 \rfloor$$ and/or $$\lceil n / 2 \rceil$$, the implied $$h_i(n)$$ also check out. So we need: $$a_1 b_1^p = 4 \cdot (1 / 2)^p = 1$$ Thus $$p = 2$$, and: $$T(n) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{u^2 du}{u^3 \ln u} \right) \right) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{du}{u \ln u} \right) \right) = \Theta(n^2 \ln \ln n)$$ (The integral as given with lower limit 1 diverges, but the lower limit should really be the $$n$$ for which the recurrence starts being valid; check the original paper.)

(The help of maxima with the algebra is gratefully aknowledgedacknowledged)

The Akra-Bazzi method

The Akra-Bazzi method gives asymptotics for recurrences of the form: $$T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for x \ge x_0}$$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $$h_i(x)$$ can cater for divisions that don't come out exact, for example. The conditions for applicability are:

• There are enough base cases to get the recurrence going
• The $$a_i$$ and $$b_i$$ are all constants
• For all $$i$$, $$a_i > 0$$
• For all $$i$$, $$0 < b_i < 1$$
• $$\lvert g(x) \rvert = O(x^c)$$ for some constant $$c$$ as $$x \rightarrow \infty$$
• For all $$i$$, $$\lvert h_i(x) \rvert = O(x / (\log x)^2)$$
• $$x_0$$ is a constant

Note that $$\lfloor b_i x \rfloor = b_i x - \{b_i x\}$$, and as the sawtooth function $$\{ u \} = u - \lfloor u \rfloor$$ is always between 0 and 1, replacing $$\lfloor b_i x \rfloor$$ (or $$\lceil b_i x \rceil$$ as appropiate) satisfies the conditions on the $$h_i$$.

Find $$p$$ such that: $$\sum_{1 \le i \le k} a_i b_i^p = 1$$ Then the asymptotic behaviour of $$T(x)$$ as $$x \rightarrow \infty$$ is given by: $$T(x) = \Theta \left( x^p \left( 1 + \int _1^x \frac{g(u)}{u^{p + 1}} du \right) \right)$$

Example

As an example, take the recursion for $$n \ge 5$$, where $$T(0) = T(1) = T(2) = T(3) = T(4) = 17$$: $$T(n) = 9 T(\lfloor n / 5 \rfloor) + T(\lceil 4 n / 5 \rceil) + 3 n \log n$$ The conditions are satisfied, we need $$p$$: $$9 \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1$$ As luck would have it, $$p = 2$$. Thus we have: $$T(n) = \Theta \left( n^2 \left(1 + \int_1^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$

(The help of maxima with the algebra is gratefully aknowledged)

The Akra-Bazzi method

The Akra-Bazzi method gives asymptotics for recurrences of the form: $$T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for x \ge x_0}$$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $$h_i(x)$$ can cater for divisions that don't come out exact, for example. The conditions for applicability are:

• There are enough base cases to get the recurrence going
• The $$a_i$$ and $$b_i$$ are all constants
• For all $$i$$, $$a_i > 0$$
• For all $$i$$, $$0 < b_i < 1$$
• $$\lvert g(x) \rvert = O(x^c)$$ for some constant $$c$$ as $$x \rightarrow \infty$$
• For all $$i$$, $$\lvert h_i(x) \rvert = O(x / (\log x)^2)$$
• $$x_0$$ is a constant

Note that $$\lfloor b_i x \rfloor = b_i x - \{b_i x\}$$, and as the sawtooth function $$\{ u \} = u - \lfloor u \rfloor$$ is always between 0 and 1, replacing $$\lfloor b_i x \rfloor$$ (or $$\lceil b_i x \rceil$$ as appropiate) satisfies the conditions on the $$h_i$$.

Find $$p$$ such that: $$\sum_{1 \le i \le k} a_i b_i^p = 1$$ Then the asymptotic behaviour of $$T(x)$$ as $$x \rightarrow \infty$$ is given by: $$T(x) = \Theta \left( x^p \left( 1 + \int _1^x \frac{g(u)}{u^{p + 1}} du \right) \right)$$

Examples

As an example, take the recursion for $$n \ge 5$$, where $$T(0) = T(1) = T(2) = T(3) = T(4) = 17$$: $$T(n) = 9 T(\lfloor n / 5 \rfloor) + T(\lceil 4 n / 5 \rceil) + 3 n \log n$$ The conditions are satisfied, we need $$p$$: $$9 \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1$$ As luck would have it, $$p = 2$$. Thus we have: $$T(n) = \Theta \left( n^2 \left(1 + \int_1^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$

Another example is the following for $$n \ge 2$$: $$T(n) = 4 T(n / 2) + n^2 / \lg n$$ We have $$g(n) = n^2 / \ln n = O(n^2)$$, check. We have that there is a single $$a_1 = 4$$, $$b_1 = 1 / 2$$, which checks out. Assuming that the $$n / 2$$ is really $$\lfloor n / 2 \rfloor$$ and/or $$\lceil n / 2 \rceil$$, the implied $$h_i(n)$$ also check out. So we need: $$a_1 b_1^p = 4 \cdot (1 / 2)^p = 1$$ Thus $$p = 2$$, and: $$T(n) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{u^2 du}{u^3 \ln u} \right) \right) = \Theta\left(n^2 \left( 1 + \int_2^n \frac{du}{u \ln u} \right) \right) = \Theta(n^2 \ln \ln n)$$ (The integral as given with lower limit 1 diverges, but the lower limit should really be the $$n$$ for which the recurrence starts being valid; check the original paper.)

(The help of maxima with the algebra is gratefully acknowledged)

1

The Akra-Bazzi method

The Akra-Bazzi method gives asymptotics for recurrences of the form: $$T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for x \ge x_0}$$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms" $$h_i(x)$$ can cater for divisions that don't come out exact, for example. The conditions for applicability are:

• There are enough base cases to get the recurrence going
• The $$a_i$$ and $$b_i$$ are all constants
• For all $$i$$, $$a_i > 0$$
• For all $$i$$, $$0 < b_i < 1$$
• $$\lvert g(x) \rvert = O(x^c)$$ for some constant $$c$$ as $$x \rightarrow \infty$$
• For all $$i$$, $$\lvert h_i(x) \rvert = O(x / (\log x)^2)$$
• $$x_0$$ is a constant

Note that $$\lfloor b_i x \rfloor = b_i x - \{b_i x\}$$, and as the sawtooth function $$\{ u \} = u - \lfloor u \rfloor$$ is always between 0 and 1, replacing $$\lfloor b_i x \rfloor$$ (or $$\lceil b_i x \rceil$$ as appropiate) satisfies the conditions on the $$h_i$$.

Find $$p$$ such that: $$\sum_{1 \le i \le k} a_i b_i^p = 1$$ Then the asymptotic behaviour of $$T(x)$$ as $$x \rightarrow \infty$$ is given by: $$T(x) = \Theta \left( x^p \left( 1 + \int _1^x \frac{g(u)}{u^{p + 1}} du \right) \right)$$

Example

As an example, take the recursion for $$n \ge 5$$, where $$T(0) = T(1) = T(2) = T(3) = T(4) = 17$$: $$T(n) = 9 T(\lfloor n / 5 \rfloor) + T(\lceil 4 n / 5 \rceil) + 3 n \log n$$ The conditions are satisfied, we need $$p$$: $$9 \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1$$ As luck would have it, $$p = 2$$. Thus we have: $$T(n) = \Theta \left( n^2 \left(1 + \int_1^n \frac{3 u \log u}{u^3} du \right) \right) = \Theta(n^2)$$

(The help of maxima with the algebra is gratefully aknowledged)