big-O notation: parenthesis for function calls, explicit multiplication #71167
Conversation
|
r? @shepmaster (rust_highfive has picked a reviewer for you, use r? to override) |
| @@ -644,7 +643,7 @@ impl<T: Ord> BinaryHeap<T> { | |||
| /// The remaining elements will be removed on drop in heap order. | |||
| /// | |||
| /// Note: | |||
| /// * `.drain_sorted()` is O(n lg n); much slower than `.drain()`. | |||
| /// * `.drain_sorted()` is `O(n * lg(n))`; much slower than `.drain()`. | |||
There was a problem hiding this comment.
I don't know what lg is supposed to mean here. Is it log with a typo, or is it supposed to indicate a particular base?
There was a problem hiding this comment.
this is the only place it is used here, i assume it is a typo
There was a problem hiding this comment.
https://www.math10.com/en/algebra/logarithm-log-ln-lg.html suggests that lg == log base 10
https://mathworld.wolfram.com/Lg.html suggests it might mean log base 2
There was a problem hiding this comment.
I mean anyway the difference between base 2 and base 10 is a constant factor, so in the context of big-O the base just doesn't matter... but then there are two places in the docs that explicitly give a base in big-O.
There was a problem hiding this comment.
So, I changed this here to log and removed the two explicitly given bases.
| @@ -40,7 +40,7 @@ use UnderflowResult::*; | |||
| /// performance on *small* nodes of elements which are cheap to compare. However in the future we | |||
| /// would like to further explore choosing the optimal search strategy based on the choice of B, | |||
| /// and possibly other factors. Using linear search, searching for a random element is expected | |||
| /// to take O(B log<sub>B</sub>n) comparisons, which is generally worse than a BST. In practice, | |||
| /// to take O(B * log<sub>B</sub>(n)) comparisons, which is generally worse than a BST. In practice, | |||
There was a problem hiding this comment.
Elsewhere we are using log_2 to indicate the base, so this is inconsistent. But for now I decided not to change this.
|
@bors r+ rollup |
|
📌 Commit 818bef5 has been approved by |
|
Thanks! |
Rollup of 6 pull requests Successful merges: - rust-lang#70467 (Use `call` instead of `invoke` for functions that cannot unwind ) - rust-lang#71070 (rustbuild: Remove stage 0 LLD flavor workaround for MSVC) - rust-lang#71167 (big-O notation: parenthesis for function calls, explicit multiplication) - rust-lang#71238 (Miri: fix typo) - rust-lang#71242 (Format Mailmap To Work With GitHub) - rust-lang#71243 (Account for use of `try!()` in 2018 edition and guide users in the right direction) Failed merges: r? @ghost
I saw
O(n m log n)in the docs and found that really hard to parse. In particular, I don't think we should use blank space as syntax for both multiplication and function calls, that is just confusing.This PR makes both multiplication and function calls explicit using Rust-like syntax. If you prefer, I can also leave one of them implicit, but I believe explicit is better here.
While I was at it I also added backticks consistently.