-
Notifications
You must be signed in to change notification settings - Fork 251
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[Merged by Bors] - feat: Asymptotic order of divide-and-conquer recurrences (Akra-Bazzi theorem) #6583
Conversation
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This looks great, thanks! Sorry for the delay with the review.
Another question I forgot to mention is if it should be in the |
I agree that filing this under "computability" is a bit of a stretch but yes, let's wait until there is a bit more material about complexity and algorithms! |
Thanks again for the review -- it took me more time than I thought to get around to implementing the changes, but this is now ready for another round of reviews! |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This looks great!
bors d+
✌️ dupuisf can now approve this pull request. To approve and merge a pull request, simply reply with |
bors r+ |
…theorem) (#6583) This PR proves the [Akra-Bazzi theorem](https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method), which gives the asymptotic order of divide-and-conquer recurrences of the form ``` T n = (∑ i in Fin k, a i * T (r i n)) + g n ``` where `T : ℕ → ℝ`, and where `r i n` is close to `b i * n` for a set of coefficients `b : Fin k → ℝ`. These recurrences arise mainly in the analysis of divide-and-conquer algorithms such as mergesort or Strassen's algorithm for matrix multiplication. Note that the traditional proof first proves a continuous version (i.e. for `T : ℝ → ℝ`) and then discretizes it to get a version that is relevant for algorithms. Here we prove the discrete version directly, which shortens the proof considerably.
Build failed: |
bors r+ |
…theorem) (#6583) This PR proves the [Akra-Bazzi theorem](https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method), which gives the asymptotic order of divide-and-conquer recurrences of the form ``` T n = (∑ i in Fin k, a i * T (r i n)) + g n ``` where `T : ℕ → ℝ`, and where `r i n` is close to `b i * n` for a set of coefficients `b : Fin k → ℝ`. These recurrences arise mainly in the analysis of divide-and-conquer algorithms such as mergesort or Strassen's algorithm for matrix multiplication. Note that the traditional proof first proves a continuous version (i.e. for `T : ℝ → ℝ`) and then discretizes it to get a version that is relevant for algorithms. Here we prove the discrete version directly, which shortens the proof considerably.
Pull request successfully merged into master. Build succeeded: |
…theorem) (#6583) This PR proves the [Akra-Bazzi theorem](https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method), which gives the asymptotic order of divide-and-conquer recurrences of the form ``` T n = (∑ i in Fin k, a i * T (r i n)) + g n ``` where `T : ℕ → ℝ`, and where `r i n` is close to `b i * n` for a set of coefficients `b : Fin k → ℝ`. These recurrences arise mainly in the analysis of divide-and-conquer algorithms such as mergesort or Strassen's algorithm for matrix multiplication. Note that the traditional proof first proves a continuous version (i.e. for `T : ℝ → ℝ`) and then discretizes it to get a version that is relevant for algorithms. Here we prove the discrete version directly, which shortens the proof considerably.
This PR proves the Akra-Bazzi theorem, which gives the asymptotic order of divide-and-conquer recurrences of the form
where
T : ℕ → ℝ
, and wherer i n
is close tob i * n
for a set of coefficientsb : Fin k → ℝ
. These recurrences arise mainly in the analysis of divide-and-conquer algorithms such as mergesort or Strassen's algorithm for matrix multiplication.Note that the traditional proof first proves a continuous version (i.e. for
T : ℝ → ℝ
) and then discretizes it to get a version that is relevant for algorithms. Here we prove the discrete version directly, which shortens the proof considerably.