# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | atcoder_official | 163 |
3 | Um_nik | 162 |
3 | maomao90 | 162 |
5 | adamant | 157 |
5 | -is-this-fft- | 157 |
5 | djm03178 | 157 |
8 | awoo | 155 |
9 | TheScrasse | 154 |
10 | Dominater069 | 153 |
Name |
---|
Learned about Akra-Bazzi theorem a year ago. Was fascinated by how useless it is.
Haha, at least it makes derivations "using" the master theorem more rigorous (i.e., ignoring floors/ceils). When I learnt about it, on the other hand, I was searching for a master-theorem-like result that handles multiple recursive terms, so I did find it quite useful.
I almost never saw any direct application of Akra-Bazzi outside of artificial academic exercises actually.
The only "real-life" example I know of a similar recurrence that actually exists is in the median of medians algorithm for finding $$$k$$$-th order statistics in deterministic $$$\Theta(n)$$$, where the recurrence is
But in this case, it's much easier to prove the result by induction then by invoking the theorem. I'm yet to see any "real-life" example where the resulting complexity is actually $$$O(x^p)$$$ with a non-trivial $$$p$$$.
For me, the main appeal is the presence of error terms. Master theorem as it is doesn't apply to pretty much any recurrence in CS. To get rid of the floors and ceils, you need a stronger version of the master theorem, which is a subcase of the Akra-Bazzi theorem.
About real life applications: I remember writing an algorithm for some CS problem in a university course which required a non-trivial application of the Akra-Bazzi theorem (induction still worked but it was hard to guess). I unfortunately don't exactly remember the problem, but I might search for it eventually.
Idk, I feel like "don't be pedantic and ignore small perturbations" approach is more sensible, as it always works on practice...
I see the appeal for rigorous academic research maybe, but practically I don't think you will ever need Akra-Bazzi, unless you have several distinct $$$b_i$$$, or $$$g(x)$$$ is $$$x^p$$$ multiplied by some unorthodox function, such as $$$\frac{1}{\log x}$$$...
Ah, about the unorthodox $$$g$$$ comment, you can find many divide and conquer problems where we often have $$$g(n) = n^a \log^b n$$$ for some choice of $$$a, b$$$ due to sqrt decomposition or FFT or some other non-trivial algorithm in the combine step. $$$b$$$ can be negative in cases where you can skip over chunks while doing dp or something.
The example I was talking about had multiple distinct $$$b_i$$$-s, I'll try to dig that up.
Some heuristic explanation for the theorem. Assume that $$$|h_i(x)| \ll x$$$ and $$$T(x) \in O(x^p)$$$ for some $$$p$$$. Then,
which rewrites as
Now, let $$$p_1$$$ be the solution to $$$1 = \sum\limits_{i=1}^k a_i b_i^p$$$, and $$$p_2$$$ be the infimum $$$p$$$ such that $$$g(x) \in O(x^{p})$$$, and let $$$p = \max(p_1, p_2)$$$.
Unless $$$p_1 = p_2$$$, the larger values will dominate the smaller one, hence $$$T(x) \in O(\max(x^{p}, g(x)))$$$.
In particular, in a similar fashion to the master theorem, it should mean that
I suppose it also means that only when $$$p_1 = p_2$$$, the solution is given by
but I fail to provide a confident intuitive explanation for this case. It probably can be done by considering the finite difference $$$G(x) - G(x-1)$$$, where $$$G(x) = \frac{T(x)}{x^p}$$$, and finding out that it's asymptotically equivalent to $$$\frac{g(x)}{x^{p+1}}$$$.