0
$\begingroup$

I read the concept about dynamical resizing hash table from this lecture. And for my understanding, it claims that the average run time of all insertions is $O(1)$ for each iteration.

Now, suppose we try to handle $n$ consecutive insertions and $n$ is not know in advance, so there might be several resizing before we finishing all the insertions.

In this case, is the average run time of all insertions still $O(1)$?

$\endgroup$
0
$\begingroup$

Yes; as done in the lecture you have linked, this is shown using amortized analysis. The intuition is that even though resizing take $O(m)$ (where $m$ is the size of the table at the time of resizing), this operation occurs more infrequently the more times we have already resized.

Even if $n$ is not known in advance, as is the case in most practical applications of hashtables, the same amortized analysis holds. This is a simple result of the fact that in the analysis, the cost of the resize operation is divided among all insertions which occurred before the resizing operation. Hence, every time we resize the table, we have already achieved our $O(1)$ average runtime by the analysis provided. Any additional insertions we perform before the next resize will of course each be done in $O(1)$ time, so on average, each of the $n$ insertions takes $O(1)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.