4 ms·
I read some of the scribe notes on succinct data structures from the link, it jumped out at me as something interesting. But going from `O(n)` to `n + o(n)` doe
by titanomachy 10y ago
I read some of the scribe notes on succinct data structures from the link, it jumped out at me as something interesting. But going from `O(n)` to `n + o(n)` doesn't seem especially game-changing -- what lead you to describe it as "miraculously powerful"?
- jerf 10y agoThe constant reduction is amazing, for those precise use cases you can afford to use them. Not all linear is created equal. O(10n) = O(n/10), but in practice the performance difference of the inner expressions can be a huge difference. (Note that is a correct usage of the O notation; because of the fact that those two things are equal we generally just use O(n) because for clarity you might as well use the simplest member of the equivalence class defined by the O notation, but it is still valid to write O(n/10). It's just an error to treat it as anything other than equal to O(n).)