9 ms·
All of the C++ algorithms list complexity guarantees, I believe. This saga stunned me to learn that C doesn’t seem to do this.
by BenFrantzDale 6y ago
All of the C++ algorithms list complexity guarantees, I believe. This saga stunned me to learn that C doesn’t seem to do this.
- tedunangst 6y agoAre there complexity guarantees for std::istream::operator>>?
- rtpg 6y agoIn the standard there's things like "exactly N operations", but not seeing stuff for `istream`. There's like... an explanation of how things should work and I imagine you can derive complexity from it, but I think `istream` is a bit special since you're talking about this wrapper for (potentially) an arbitrary input source. [0]: https://eel.is/c++draft/alg.move#15 https://eel.is/c++draft/alg.move#15 [1]: https://eel.is/c++draft/input.streams#istream.extractors-7 https://eel.is/c++draft/input.streams#istream.extractors-7
- mkl 6y agoNo, or at least not in general, because you can overload it for your custom types with whatever terrible implementation you like.
- loeg 6y agoThis is true in essentially the same way for C's FILE, which is the point I think Ted is insinuating.
- 0xcde4c3db 6y agoIt's easy to forget that the original C standards were largely codifying existing practice during an era when using gets() [1] was existing practice. The world wasn't quite ready for Ada, I guess. Best-laid plans of mice and men etc. etc.. Also, keep an eye out for "amortized" complexity. This does have a legitimately rigorous definition, but for latency-bound paths it can practically amount to "O(whatever), except for the particular invocations that are far, far worse under unspecified conditions". [1] https://www.man7.org/linux/man-pages/man3/gets.3.html#BUGS https://www.man7.org/linux/man-pages/man3/gets.3.html#BUGS
- lostcolony 6y ago...I fully plan to use "O(whatever)". Not sure for what. But, yes. (naive) Quicksort's amortized complexity being O(nlogn), but its O(n^2) on already sorted data, is all I ever needed to learn to take away that lesson. When sorting already sorted data is worse than sorting randomized data, it's a quick realization that "amortized cost" = "read the fine print".
- nyanpasu64 6y agoQuicksort as O(n log n) is not amortized complexity, but average runtime for random data.
- lostcolony 6y agoFair point; I'm confusing my terminology. Analogy and realization still holds.
- virgilp 6y agoAlso, already sorted data.. in reverse order. If it's already sorted in the right order, quicksort takes linear time. This is an important difference - data you use might indeed often be appropriately sorted, but in practice will seldom be sorted in reverse order.
- SuchAnonMuchWow 6y agoIf it's already sorted in the right order, quicksort runs in O(n log n). quicksort is O(n log n) bestcase, O(n*n) worstcase.
- virgilp 6y agoActually, yeah, my original reply was dumb, I forgot quicksort :) It can be n*n for properly-sorted arrays too, depending on pivot selection (for randomized pivot selection, it's n log n).
- TheOtherHobbes 6y agoThat's because C is just a wrapper for machine code on a cheap PDP-11, and cheap PDP-11s didn't have enough RAM to do complexity.