News for hackers. Stuff that matters.
[deleted]
Re:Accidentally Quadratic by btilly on Thursday March 12, 2015 @07:03PM (#9194584)
You're wrong. What's worse, you're being pedantic about being wrong.

If your hash function works properly, and you are dynamically resizing your hash by a constant fraction whenever it gets too full, you can bound the probability of hash collisions above, and bound the number of expected hash collisions by a constant. As is standard in resized data structure, the resizing is individually O(n) with frequency O(1/n) for an amortized cost of O(1) per insert.

Put all of that together, and the amortized average cost of an insert into the hash is O(1). This is a well-known standard result, and is the reason why hashes are useful.

Re:Accidentally Quadratic by eonwe on Friday March 13, 2015 @05:30AM (#9196282)
To be a pedantic here, I don't think term amortized average cost is useful.

For what I've understood, average cost means average over all possible random inputs. So for specific set inputs, the cost can be larger than that.

Amortized cost means the average cost of the operation over any combination of inputs. So for specific set of inputs, the cost is the stated.

For hash table insertion, both the amortized and average cost can be O(1) with linked-list confliction resolution, but whereas average time of a lookup operation is O(1), amortized is larger (I don't know if there's analysis on this, but O(n) seems correct by gut-feeling).

Re:Accidentally Quadratic by btilly on Friday March 13, 2015 @05:14PM (#9200095)
You have understood incorrectly. Here is http://www.cs.cornell.edu/courses/cs312/2006sp/lectures/lec1... on the topic:

Amortized analysis refers to determining the time-averaged running time for a sequence of operations.

Note that you are averaging over a sequence of operations, and not any combination of inputs. As that article goes on to explain, amortized analysis is the right thing to use for figuring out the total running time of a sequence of operations.

Let's be concrete. In the case of a dynamically resized hash, the bound on an individual hash insertion when the hashing function works is O(n) because you could be looking at the unlucky insertion that resized the hash. The amortized cost is O(1) because you get to spread that expensive resize over many individual operations. If you're building a hard real time system, you should focus on the O(n) and not use that data structure. If you just want to build a hash table, the O(1) is what matters.

What about the amortized cost of many random hash lookups with linked-list conflict resolution? The distribution of buckets with different numbers of items approximately follows a Poisson distribution. From that we can estimate the average number of comparisons. And find out that the amortized cost is on average O(1).

Re:Accidentally Quadratic by Iftheshoefits on Thursday March 12, 2015 @06:48PM (#9194505)
That's a bit pedantic, innit. It isn't strictly O(1) but with any reasonable implementation the collision resolution algorithm will make it have an amortized O(M), where M << N and therefore effectively constant.
Re:Accidentally Quadratic by teraflop on Thursday March 12, 2015 @07:00PM (#9194566)
What does "a little more than constant time" mean? Like inverse-Ackermann or something?
Re:Accidentally Quadratic by ssunstruck on Thursday March 12, 2015 @06:43PM (#9194479)
Still less than O(n)