> Everything is O(1) if N is constant, including log(N), N^2, 2^N, N!, etc.
Not even close. 2^k is not O(1) by virtue of N being constant. Only 2^N.
This has been covered above. It is more common to consider the complexity of hash table operations in terms of the number of operations, or the size of the table; the size of the key is very often constant. These are different variables; the constant size of the key does not trivialize the complexity of inserting N items each with a constant key size.
Here, the relevant key is the output of the hash function though -- that's what you need to increase in order to ensure you can reach all buckets. And that (k) must increase with the table size. So it is not constant and depends on n (table size).
Yes. Everything is O(1) if N is constant, including log(N), N^2, 2^N, N!, etc. That's a tautology.
> Everything is O(1) if N is constant, including log(N), N^2, 2^N, N!, etc.
Not even close. 2^k is not O(1) by virtue of N being constant. Only 2^N.
This has been covered above. It is more common to consider the complexity of hash table operations in terms of the number of operations, or the size of the table; the size of the key is very often constant. These are different variables; the constant size of the key does not trivialize the complexity of inserting N items each with a constant key size.
Here, the relevant key is the output of the hash function though -- that's what you need to increase in order to ensure you can reach all buckets. And that (k) must increase with the table size. So it is not constant and depends on n (table size).
Earlier discussion: https://news.ycombinator.com/item?id=9807739
6 replies →