PR !4#6583: feat: Asymptotic order of divide-and-conquer ...

Stream: triage

[Random Issue Bot]

Today I chose PR 6583 for discussion!

feat: Asymptotic order of divide-and-conquer recurrences (Akra-Bazzi theorem)
Created by @Frédéric Dupuis (@dupuisf) on 2023-08-15
Labels: awaiting-review

Is this PR still relevant? Any recent updates? Anyone making progress?

[Eric Rodriguez]

Oh wow, this is mega cool! I had no clue it had an actual name, all the CS literature I'd ever seen calls it just "the master theorem" which is a pretty useless name

[Frédéric Dupuis]

Thanks! What I've seen called the "master theorem" is actually a special case of this, where all the blocks are of the same size, $g$ is restricted to be in $\Theta(n^k)$, and doesn't handle approximate block sizes (or only rounding up/down).