Solution Set 4

Solution 1

a- Kim is unfortunately using a bad hash function. Her function computes the sum of integers from 1 to n and hashes n to the slot numbered sum. To calculate the hash of a given k, the loop would run for k steps. The function thus has a complexity of O(k). Note, how a hash table using this hash function would fail to provide O(1) insert and retrieval operations.

b- The hash function is computing the sum of numbers from 1 to k. We already know that the summation of consecutive numbers from 1 to k can be represented by the following formula

$$sum =\frac{k(k+1)}{2}$$ ...