5 ms·

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 input

by eonwe 12y ago

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

btilly 12y ago
You have understood incorrectly. Here is http://www.cs.cornell.edu/courses/cs312/2006sp/lectures/lec18.html 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).

by eonwe 12y ago

btilly 12y ago

You have understood incorrectly. Here is http://www.cs.cornell.edu/courses/cs312/2006sp/lectures/lec18.html 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).