4 ms·
No O(√N) is O(N^0.5)
by knappa 10y ago
No O(√N) is O(N^0.5)
- bogomipz 10y agoSorry yes of course, that's what I meant. But O(1) is the amortization with the average being O(N^0.5)
- njaremko 10y agoIf you read the linked blog post about cache speed (http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-part-i http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-p...) it'll make a lot more sense.
- bogomipz 10y agoOh thanks, also a good read. The author in this post however states: "That I use Big O to analyze time and not operations is important." This strikes me as an odd statement though as Big O is generally meant to describe a run time or space not operations. What am I missing?
- njaremko 10y agoBig O is really just saying that a function f(n) belongs to O(g(n)) if 0 <= f(n) <= c*g(n) for some C >= 0. When he says he's using big O for time and not operations, he's saying that n is time (as opposed to operations)
- bogomipz 10y agoSure, I just thought it was an odd statement to be explicit about as it the usual case to have it express time and not operations.
- lorenzhs 10y agoNot quite. You're usually measuring time in a specific model. Most often, that's the RAM model, where memory access and arithmetic operations take constant time (defined as one time step). The author is using a different model, but doesn't formally define it and instead tries to make it fit wall-clock time. That requires far more elaborate modelling, ends up being extremely complicated, and usually doesn't yield all that much additional insight. That's why computer scientists usually use the RAM model - it captures the most important aspects of computers, but omits others as they're hard to model accurately. The memory hierarchy is one of these. Some models where such things are studied in more details include the external memory model (which has a two-level hierarchy - cache and main memory, or main memory and disk) and cache-oblivious models. Most of the time, you don't need that extra information, though, and the RAM model suffices.
- bogomipz 10y agoThanks for clearing that up. I'm catching up on the other discussion now : )
- lorenzhs 10y agoYou're making the same mistake that the author of that article is making. That condition only has to hold for sufficiently large values of n - i.e., n ≥ n₀ for some n₀.
- lorenzhs 10y agoThat article is currently being discussed at https://news.ycombinator.com/item?id=12383012 https://news.ycombinator.com/item?id=12383012 - suffice it to say, there are numerous issues with the author's understanding of Big-O notation.
- knappa 10y agoThe amortization is the average and is O(1). The claim is that the worst case (when the table becomes relatively saturated and a resize is required) is O(N^0.5). I don't really buy that and the supplied link doesn't really make that claim either. By the argument in that link, it should be O(N^1.5) for rehashing. (Usually we think that copying N items is O(N), but he makes an argument from physics which I haven't thought through.)
- marcosdumay 10y agoThe time being amortized to O(1) means that not only the average is O(1), but it is guaranteed that your use case will average into O(1) if you do enough operations. There is no chance you'll get an O(n^0.5) run just because you got bad data or unlucky.