Problem Set 4

Question 1

Kim is new to programming and designs the following hash function for her hash table.

    int computeHash(int key) {
        int hash = 0;
        for (int i = 1; i <= key; i++) {
            hash += i;
        }
        return hash;
    }

a- What is the time complexity of the hash function?

b- Can we make the hash function take constant time?

c- What is the space requirements/complexity if Kim chooses to stick with her hash function and wants to ensure no collisions happen?

Note: The solution to the following questions is not provided in the next lesson. These questions are just for the user to solve by themselves.

Question 2

We talked about one-dimensional arrays. How would the complexity of accessing an element be affected in a 2-dimensional array?

Question 3

We have a class called N-Dimensional Array. The class takes in a parameter n and creates an n-dimensional array. What would be the time complexity of accessing the elements of the array in the nth dimension?