3 ms·
I'm a little disappointed that I bothered to read what turned out to be a massive act of pedantry. A few sections are devoted to showing that O(log32(n)) is th
by kbenson 9y ago
I'm a little disappointed that I bothered to read what turned out to be a massive act of pedantry.
A few sections are devoted to showing that O(log32(n)) is the same as O(log(n)). This is entirely correct, as shown, because the difference between them is reducible to a constant multiplier, which big-O notation does not care about. It's also, from the problematic sources given, and entirely made up argument, given that I didn't find O(log32(n)) mentioned in any of them that I was able to view. Plenty of notes in them about it being logarithmic though...
I understand making sure people know that it's not constant time, but when all the examples of problematic descriptions you give make sure to say that it is logarithmic time and then go on to explain why it's "effectively constant", you're railing against a non-issue with an absurdly complicated argument.
- dom0 9y ago> you're railing against a non-issue with an absurdly complicated argument. It's not really the correct kind of argument. Landau notation is for analyzing asymptotic behaviour of functions; this makes them fit as sets of functions for many purposes in theoretical compsi, but it's simply the wrong approach for practical, "in the field" comparison of implemented algorithms. It only has some merit there to state... well, asymptotic behaviour, like the complexity of a hash-table lookup or deleting an arbitrary element of a vector.
- KirinDave 9y agoWords may be relative, but that's why we set up systametized math notation to appeal to when we need to start characterizing the precise nature of algorithms and systems. To argue that this is act of pedantry is to argue that any form of canoncial notation to describe the essential nature of algorithms is itself pedantry. It's to suggest bigO notation itself is pedantry and by extension so is it's defense. In the face of this, I'd say, "If you don't like it, don't use it. But many people do find it useful and it's corrosive in the extreme to demand the right to redefine it for what amounts to marketing purposes." Scala's got a bunch of actors in it's community that do this; and it's frustrating when you're trying to evaluate the ecosystem. The asymptotic boundaries of algorithms ARE theoretical tools that can be misleading. For example, how many people incorrectly suggest that quicksort is asymptotically faster than merge sort? It's not. But the response to this should not be to vaguely redefine the terms. The response to this should be to quantify the implementation's docs with real metrics.
- kbenson 9y ago> In the face of this, I'd say, "If you don't like it, don't use it. But many people do find it useful and it's corrosive in the extreme to demand the right to redefine it for what amounts to marketing purposes." But as I pointed out, in all the examples provided in the article as evidence of this behavior, not only did they not mention O(log32(n)), they often (possibly always in the links presented) did specifically call out running time as logarithmic prior to mentioning what that meant in practice. > But the response to this should not be to vaguely redefine the terms. The response to this should be to quantify the implementation's docs with real metrics. This is not a case of vague wording being used, it's a case of exact wording being used and additional context being provided. Edit: I noticed some of the examples weren't as upfront about the time complexity, I was mistakenly seeing what was presented for Lists as applying to Vectors. In lieu of that, I agree that they could, and should, be more up-front about the theoretical time and the practical time if they plan to continue using "effectively constant" in documentation.
- KirinDave 9y agoI've seen numerous examples of "essentially constant time" on slide decks, presentations and talks. But I'd argue even if you did do this after a prior disclaimer, it's still somewhat misleading. It's adopting language that sounds very similar and creating greater confusion. > This is not a case of vague wording being used, it's a case of exact wording being used and additional context being provided. And yet the confusion persists. And I can point to enthusiastic jr. engineers who don't fully grasp the difference, and that were somewhat surprised when I corrected them (the equivalence of log32 and log2 should be enough but...) Similar stories abound from multiple actors in the world of Scala. Another great example is the (now infamous) "non-blocking backpressure." Same principle, taking well-understood industry terms (some of which even have precise definitions lifted from more rigorous disciplines) and wrangling them into something almost unrecognizable.