Comment by ggchappell | Hacker News Reader

Comment by ggchappell | Hacker News Reader

Okay, he is saying that the time required for an arithmetic operation is proportional to the number of bits operated on.

This is true, and it is applicable to other concepts besides hash tables. Can you sort n numbers in O(n log n)? Well a comparison is not really constant-time, in the wall-clock sense of time. If the n numbers are distinct, then each is going to need at least O(log n) bits. So a comparison is O(log n) by the clock, and our sort becomes O(n log n log n).

Part of the solution is to be more precise. For example, when we say that Merge Sort is O(n log n), we usually do not mean that it takes that long to run; we mean that it can require that many comparisons. Counting primitive operations can be useful, even if those operations are not constant-time from a wall-clock point of view. And as long as we are clear on what the primitive operations are, everything is fine.

By the way, there is another problem with the statement that hash-table insertion is amortized constant-time: what if all the keys end up being in the same bucket? The true statement is that HT insertion is amortized constant-time for average data. (So it's constant-time on average on average. :-)

You should not be using n for the number of bits and n for the size of the input.

It may take longer to multiply 128 bit data structures than 64 bit data structures, but it is constant with respect to the size of the hash table.

> but it is constant with respect to the size of the hash table.

Exactly. That is the whole key to complexity analysis.

Otherwise you end up drowning in details without getting more meaningful answers.

You're analyzing the hash table algorithm, not the hashing algorithm used to produce the keys.

My post specifically refers to vectorization where you may use the fact that you can multiply 4 pairs of 16-bit integers in the time it takes to multiply a pair of 64-bit integers. So, you could operate four 16-bit hash tables in the time it takes to operate a 64-bit hash table.

That's all somewhat theoretical sure, but the point is to challenge your assumptions. (People do use vectorization, right now.)

"That's all somewhat theoretical sure, but the point is to challenge your assumptions. (People do use vectorization, right now.)"

You're assuming that people are not aware that multiplication is not always a constant-time operation. That assumption generally doesn't hold among people with any sort of academic CS background. Multiplication algorithms - and the fact that they were typically O(N) in number of bits - were covered in my intro machine architectures course.

In practice, there are many, many other things that can negatively impact hash table performance in a much bigger way. Like cache misses - one cache miss costs far more than an integer multiplication. Or interpreter overhead from using, say, Ruby instead of C (bad example, since Ruby's hashtables are implemented in C, but the general point holds). Or the difference between -O0 and -O3. Or how early versions of Java Hashtables would often devolve into linked lists because the hash function only looked at the first 8 characters of a string.

I am not sure optimization, cache misses, and interpreter overhead would obviously impact the computational complexity.

"You're assuming that people are not aware that multiplication is not always a constant-time operation."

I made no such assumption. But I suggest people consider the case of vectorization where, all of a sudden, it may matter quite a bit.

You're making a point about where we take cognitive shortcuts. Short version: don't assume the classroom example assumptions always hold in the real world.

> You should not be using n for the number of bits and n for the size of the input.

I don't see that I ever did use it for a number of bits. I said, to have n numbers with distinct values, you need O(log n) bits in each number. n is not a number of bits.

Reply on news.ycombinator.com