Блог пользователя nor

The Akra-Bazzi theorem — a generalization of the master theorem for recurrences
Автор nor, 11 месяцев назад, По-английски

https://nor-blog.codeberg.page/posts/2023-12-19-akra-bazzi-theorem/

  • Проголосовать: нравится
  • +67
  • Проголосовать: не нравится

»
11 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +104 Проголосовать: не нравится

Learned about Akra-Bazzi theorem a year ago. Was fascinated by how useless it is.

→ Ответить
  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

      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

      $$$ T(n) = T(\frac{n}{5}) + T(\frac{7n}{10})+\Theta(n). $$$

      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$$$.

      → Ответить
      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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.

        → Ответить
        • »
          »
          »
          »
          »
          11 месяцев назад, # ^ |
          ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          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}$$$...

          → Ответить
          • »
            »
            »
            »
            »
            »
            11 месяцев назад, # ^ |
            ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            → Ответить
»
11 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Some heuristic explanation for the theorem. Assume that $$$|h_i(x)| \ll x$$$ and $$$T(x) \in O(x^p)$$$ for some $$$p$$$. Then,

$$$ g(x) + \sum\limits_{i=1}^k a_i b_i^p x^p \in O(x^p), $$$

which rewrites as

$$$ \frac{g(x)}{x^p} + \sum\limits_{i=1}^k a_i b_i^p \in O(1). $$$

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

  • if $$$g(x) \in \Omega(x^c)$$$ and $$$\sum\limits_{i=1}^k a_i b_i^c < 1$$$, then $$$T(x) \in \Theta(g(x))$$$.
  • if $$$g(x) \in O(x^c)$$$ and $$$\sum\limits_{i=1}^k a_i b_i^c > 1$$$, then $$$T(x) \in \Theta(x^{p})$$$.

I suppose it also means that only when $$$p_1 = p_2$$$, the solution is given by

$$$ \frac{T(x)}{x^p} \in \Theta\left(\int\limits_0^x \frac{g(u)}{u^{p+1}} du\right), $$$

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}}$$$.

→ Ответить