# Recurrence for total number of extraneous key insertions in a hash table

I have a practice exam question that I don't know how to set up a recurrence for. It is dealing with a hash table. The question is as follows:

Suppose that a hashing strategy is designed so that it starts with an initial hash table size of $$H= 8$$. You may assume that only insertions are performed (no deletions).

Any time the hash table is going to be more than 50% full (when an attempt is made to add item $$\frac{H}{2} + 1$$ to a table of size $$H$$), the hash table size is doubled to $$2\times H$$, and then the $$\frac{H}{2}$$ keys in the previous hash table are rehashed using $$\frac{H}{2}$$ extraneous key insertions into the new table of size $$2 \times H$$. The key insertions used to initially place each key into the hash table are called necessary key insertions (these are not extraneous).

The question is asking to derive a recurrence relation $$E(H)$$ for the number of extraneous key insertions that have occurred in total up until the point in time that the hash table size is $$H$$ and to explain where the terms in the recurrence relation derive from.

If someone could help me out with this, it would provide very helpful as I am practicing for an exam that I have in a week. Thanks everyone.

I got the result $$E(H)=2\times E(\frac{H}{2})$$ because after each rehash there are $$\frac{H}{2}$$ extraneous key insertions being put into the table of size $$2\times H$$. So if the size is twice the amount of $$H$$, I figured the recurrence would be $$E(H)=2\times E(\frac{H}{2})$$. I only posted here because I was hoping someone could assist me with this because this question has me a bit stumped.

• What have you tried? It asks you to derive a recurrence relation. Have you tried to write one? Have you tried to count the number of extraneous key insertions in total, as a function of the number that occur until the most recent doubling and the number that have occurred since then? Does this give you any ideas for a recurrence relation? On this site we expect you to make a serious effort to solve the problem yourself before asking, and to show us what you've tried and where you got stuck. (This is not a "homework help site" where you share the exercise and we solve it for you.) – D.W. Nov 20 '13 at 1:53
• Hello D.W. , it is not homework, it is a practice question for an upcoming exam. Also, I attempted it and got E(H) = 2 * E(H/2) but I am not sure if this is correct. I am asking just for help as I want to know how to do a question like this for the exam. – user41580 Nov 20 '13 at 2:07
• I know it's not homework; I saw that. I stand by all of my comments. Anyway: Where did you get the $E(H) = 2 * E(H/2)$ from? What is your reasoning? Where did that come from? Don't just guess: Try to write down the justification for that equation, and see whether you buy it. If you care about getting help here, you should edit the question to show what you've tried and your reasoning. (You might also want to read the help center -- which will tell you the same thing.) – D.W. Nov 20 '13 at 2:31
• Hi @D.W. thanks again for your reply. I got that result because after each rehash there are H/2 extraneous key insertions being put into the table of size 2H. So if the size is twice the amount of H, I figured the recurrence would be E(H)=2∗E(H/2). I only posted here because I was hoping someone could assist me with this because this question has me a bt stumped. Thanks though for your response. – user41580 Nov 20 '13 at 2:34
• Again, please edit your question so that the question is self-contained and people do not need to read the comments section to understand the full question. This is not a discussion forum. I also strongly encourage you to read the help center carefully, as this site is different from most sites you have probably used before, in important ways. – D.W. Nov 20 '13 at 2:45

Your justification is flawed. There is no reason to think that the number of extraneous key insertions will necessarily be twice as much if the hash table is twice as large; you're just guessing here. When you choose a recurrence relation, you need to be able to justify it. Don't just guess.

My recommendation is that you go back to my first comment and try to answer the questions I asked there:

Have you tried to count the number of extraneous key insertions in total, as a function of the number that occur until the most recent doubling and the number that have occurred since then? Does this give you any ideas for a recurrence relation?

I don't see any evidence that you've tried to pursue that direction yet, so I suggest that you spend some quality time thinking about that avenue. If you let $n_t =$ the number of extraneous key insertions in total, $n_0 =$ the number that occur from the beginning of time until the most recent doubling, and $n_1 =$ the number that have occurred since then, can you write a formula that writes $n_t$, $n_0$, and $n_1$? Hint: When you see the answer to this question, you'll probably kick yourself. If you think about it, you'll probably find it's not as hard as you think.

Then, once you can answer that question, here is your next step. When you can come up with a formula that relates those three quantities, you might next try to think about how/whether they are related to values of the form $E(\text{something})$. Can you find any formulas for any of $n_t$, $n_0$, and $n_1$ as a function of $E(\text{something})$?

• I have attempted to count the number of extraneous key insertions in total but have not been able to. I am stuck. If you could should me how I could get started instead of telling me to perform the same steps, it would prove to be useful. I am not asking for a direct answer to the question, I want to know how to get the values and how to start each of the steps you just mentioned. – user41580 Nov 20 '13 at 2:57
• @user41580, that's exactly what I've been doing. I've been suggesting some first steps that will get you on the path and help guide you to solve the problem. – D.W. Nov 20 '13 at 2:58
• I am STILL stuck D.W. Can you further elaborate instead of just saying to do those steps? The question already tells me to do that, I have no idea how to get started. If I can't get started, how would I be able to solve the problem? – user41580 Nov 20 '13 at 3:05
• So for nt, I am still getting 2H/2 = H . How would I find the total number of extraneous key isnertions? And are nt, n0, and n1 all dependant on each other? Thanks. – user41580 Nov 20 '13 at 4:12
• Can anyone else provide assistance? Thanks – user41580 Nov 20 '13 at 17:38

If the current occupancy of the hash table is $H \geq 3$, then the hash table is of size $2^{\lceil \log_2 H \rceil + 1}$. Assuming this size is larger than $8$, this means that $2^{\lceil \log_2 H \rceil-1}+1$ entries had to be copied last time the table was enlarged, which happened upon insertion of element no. $2^{\lceil \log_2 H \rceil-1}+1$. Therefore $$E(H) = \begin{cases} 2^{\lceil \log_2 H \rceil-1}+1 + E(2^{\lceil \log_2 H \rceil-1}+1) & H \geq 5 \\ 0 & H \leq 4. \end{cases}$$ This can be solved to give $E(H) = \Theta(H)$ for $H \geq 5$.