7 ms·
Ah, this brings back the memory of my O(n^2) fiasco. I wrote a low level file system storage driver in the past. In the caching layer, there's a need to sort
by ww520 7y ago
Ah, this brings back the memory of my O(n^2) fiasco. I wrote a low level file system storage driver in the past. In the caching layer, there's a need to sort by LRU time for cache eviction. It's a minor thing not run often and I wanted to move quickly. Also since it's low level kernel mode code, I wanted the code to be simple and correct. The number of cache entries was not big. Bubble sort was adequate for small N, to get the job done quickly and simple enough to ensure correctness. Plus I could replace it later if needed. So it's done and forgotten.
Things were working fine and performance was good. Then one day Windows Explorer suddenly hung with 100% CPU for couple seconds. This was one of the worst kind of bugs. There's no crash to pinpoint the problem. Things still work most of the times, just slowed down intermittently. Luckily I was able to catch a slowdown and deliberately crashed the process in time. The call trace stopped in the bubble sort function. I immediately kicked myself - it's the classic case of O(n^2) blowup. The cache entries had been scaled up to couple thousands items and the exponential O(n^2) blowup to tens of million of iterations was having a real impact. I switched to merge sort and performance was back to normal.
Edit: I picked merge sort because the worst case was O(n log n), unlike quick sort whose worst case was O(n^2). Once burnt, needed to be extra careful with edge cases.
- vecter 7y agon^2 is polynomial, not exponential. If it was truly exponential (which a sort should never be unless you've decided to solve an arbitrary 3-SAT problem while sorting a list), then it would've blown up in your face much sooner.
- ww520 7y agoYou're correct n^2 is polynomial, not exponential. It was just an exaggerated figure of speech. BTW, O(n) and O(n log n) are also polynomial; it just doesn't have the punch to it.
- paulddraper 7y agoSo the more precise term would be quadratic. "Exponential" is indeed misused. Half the time I hear it, it is lower, like quadratic or cubic. The other half the time is higher, like combinatorial.
- emn13 7y agoCombinatorial? Seriously? The difference between exponential and cominatorial is essentially purely theoretical when it comes to computational complexity. In practice, even the difference between n and n log n is barely relevant, and the exponential and combinatorial are the exponentiation thereof. Nobody ever, ever deals with processes large enough where the difference both matters, and the process completes. Even a tiny scaling factor in the exponent and a moderate base means the point at which a unscaled combinatorial passes it will take more steps that you might as well be waiting for the heat death of the universe. But even without any scaling factors, don't underestimate the size of the numbers involved. If you had two threads, one simply counting up to some n! upper bound, and the other up to 10^n - how long do you think the minimum problem size would take for the "slow" combinatorial to actually be slower than the exponentiation? Hint: at 4GHz and 1 op/cycle... Let's just say I'm not holding my breath that our species will still be around then. And even a tiny scaling factor to the mix... I mean, if you're trying to estimate computational complexity at least, this nuance seems pointless. But quadratic vs. exponential really matters, with plausible parameters.
- paulddraper 7y agoThat's probably why it's misused so much.
- MaximumYComb 7y agoWith n = 26, the combinatorial process takes 4 times as long. 4 x 10^26 "counts". Googles SHA1 collision attack two years ago used roughly 10^19 computations. So we're off by a factor of 10^7. I'm curious if the rise of quantum computers will make the differences between exponential and combinatorial meaningful in a practical sense.
- Craighead 7y agoWhat does exponential look like then?
- blattimwind 7y ago2^n (by the virtue of Big-O, m^n is in O(2^n) for any fixed m).
- ammen99 7y agoThis is not true, consider taking the limit 3^n/2^n as n goes to infinity, the limit is infinity, hence 3^n is not O(2^n)
- aliceryhl 7y agoThis is untrue: There's no constant k such that k*2^n > 3^n for all n. In general O(a^n) is strictly stronger than O(b^n) if a > b. This is why you sometimes see complexities that are e.g. O(1.3894732894^n) in wikipedia articles on the best known cases for various algorithms.
- thaumasiotes 7y ago> In general O(a^n) is strictly stronger than O(b^n) if a > b. Typo: O(a^n) is a stronger guarantee than O(b^n) if a < b. It means nothing if a > b.
- xmprt 7y agoI took strictly stronger to mean a^n + b^n is O(a^n) so the a^n term holds more weight. The comment didn't mention anything about guarantees.
- thaumasiotes 7y agoAh, that would make sense. I actually thought the most likely intended meaning was that an algorithm in O(a^n) must take asymptotically longer than one in O(b^n) as n goes to infinity (if a > b), which isn't true. (For example, when a > b, then every algorithm in O(b^n) is also in O(a^n), but obviously no algorithm can asymptotically require more time than itself.)
- chx 7y ago> which a sort should never be There's certainly a most awesome sort algorithm which is exponential... https://www.dangermouse.net/esoteric/bogobogosort.html https://www.dangermouse.net/esoteric/bogobogosort.html They are not even sure what the complexity is but it's like O(n!^(n-k)) or O(n*(n!)^n).
- vecter 7y agoI'm aware of bogosort and its crazy variants, but let's not be ridiculous here. You could make any "sorting" algorithm arbitrarily bad if you'd like by doing such silly but useless things.
- samatman 7y agoI propose Boltzmann sort: wait around until the heat death of the universe, and a Boltzmann brain will emerge from the cosmos, and sort your values while contemplating infinity.
- thewakalix 7y agoAh, a fully general O(1) algorithm. Amazing.
- Graham24 7y agoThe very idea of O(n*(n!)^n) is going to give me nightmares.
- gdxhyrd 7y agoQuadratic, not exponential! :)
- oneplane 7y agoWould it be correct to say it's a quadratic complexity causing the run time to grow exponentially? Or is the word exponential still wrong here. My Mathematics terminology is rather.. dusty.
- bananabreakfast 7y agoYep, still wrong. Exponent != Exponential
- oneplane 7y agoI really should re-read some books. Thanks!
- boneitis 7y agoDon't fret it. Imo people are being unnecessarily curt when trying to flex their pedantry here, which we all love to do, myself included. Of course, poly still means there is an exponential in the time complexity. It's really nothing beyond the main takeaway that the usual norm to describe something as having "exponential" growth is that the number of computations increases in order of magnitude every time you add but a single item to the list of inputs.
- w0utert 7y agoQuadratic complexity causes the runtime to grow quadratically ;-) - Quadratic = x^2, e.g. 0,1,4,9,16,25,36,49,64,81 - Exponential = n^x, for example 2^x, e.g. 1,2,4,8,16,32,64,128,256 Already very bad for small x even if n=2, but for n higher than 2 you can imagine you will run out of time very, very quickly ;-P
- oneplane 7y ago
- hinkley 7y agoI got the honor to file a bug against Together's design tool. We had a project that was a monorepo with a few dozen distinct compilation units in it and some had complained that the more modules you added to the project the longer it would take to open. One person was up to half an hour and didn't even have the whole thing. I had a slow week babysitting something else so I just let it chew away in the background, while doing other things like documentation and requirements work, noting down the time, adding one more module and running it again. The last one I was willing to do took 18 hours to load. It was still running when I got back to the office the following day. To this day, I can't recall ever seeing any production performance bug with greater than n cubed complexity. This bug progressed at n to the fifth. Truly, a thing of singular beauty. Thankfully they had a workaround that dropped it to something like n^2 (30 minutes became less than 5) and a bug fix not too long after.
- mark-r 7y agoI once coded a bubble sort in an application where I expected the worst case to be n=4. Later that assumption was invalidated, but I had long ago moved on to something else. I hope the person who inherited my code doesn't still hate me.
- aflag 7y agoWhy bubble sort? I never understood its popularity. Selection sort feels a lot more intuitive to me and it's the same complexity.
- mark-r 7y agoBubble sort is the first one I learned, so I remember it the best. I never spent any time comparing any of the O(n^2) sorts so it never occurred to me to try a different one.
- deleted 7y ago[deleted]
- carlhjerpe 7y agoAnd here am I, just using what's in the standard library. of the language I'm writing. Never occured to me to try a different one.
- mark-r 7y agoThis was quite a while ago, and the library sort was QSort which had a lot of overhead due to its calling convention. Today I'd have no problem using std::sort instead.
- ynik 7y agoBubble sort is popular because it's provably optimal... under extremely restrictive circumstances: https://stackoverflow.com/a/3274203 https://stackoverflow.com/a/3274203 Those circumstances stopped being semi-relevant when even the cheapest computers started using (floppy) disk drives instead of tape drives, but somehow bubble sort is still being taught.
- sterlind 7y agoYou could also go with radix sort (O(N)), since your insertion times are presumably some kind of integer.
- ww520 7y agoYes, radix is faster. But at that point I was looking for stability and simplicity over all else. Merge sort was stable and simple to implement, with decent performance.
- hhmc 7y agoQuick sort can be made to be O(n log n) with careful choice of pivot - e.g. https://en.wikipedia.org/wiki/Median_of_medians https://en.wikipedia.org/wiki/Median_of_medians
- gpderetta 7y agobut merge sort is not in-place (at least not any remotely practical variant); heap sort is simple, in-place and O(n log n), although it is not a stable sort as merge sort.
- RomanBob 7y ago>and the exponential O(n^2) You need to look up what exponential means.