Hacker News Reader

Comment by bogomipz | Hacker News Reader

The author states:

"They allow you to insert, erase and look up things in amortized O(1) operations (O(√N) time)." Are they staying that the average time is (O(√N) and that is amortized to ~ O(1)?

I assume (O(√N) is the same as .5 multiplied by N? Is that correct? I don't think I've seen a square root in Big O notation before.

View on HN

Nah, that O(√N) comment in the article is a link to another blog post where the author claims that random memory accesses take O(√N) time.

I say "claim" because everything can be made to look like a fit on a log-log-plot. It's just memory hierarchy. (TLB misses do incur a logarithmic delay, because the page table usually uses a tree data structure, albeit with a high branching factor).

.5 multiplied by N is still O(N) time (.5 a constant factor).

O(√N) means there will be at most C*√N operations (where C is some constant factor > 0)

No O(√N) is O(N^0.5)

Sorry yes of course, that's what I meant. But O(1) is the amortization with the average being O(N^0.5)

If you read the linked blog post about cache speed (http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-p...) it'll make a lot more sense.

Oh 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?

Big 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)

Sure, 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.

Not 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.

Thanks for clearing that up. I'm catching up on the other discussion now : )

You'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₀.

That article is currently being discussed at https://news.ycombinator.com/item?id=12383012 - suffice it to say, there are numerous issues with the author's understanding of Big-O notation.

The 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.)

The 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.

Reply on news.ycombinator.com