Hash table to store a set #1

We want a data structure that supports the Set ADT:

• You can insert a new item in the set, which does nothing if the item is already there.
• You can test membership to find out if a given element is in the set or not.

In class we came up with the following idea: use a hash table of boolean values, initially all set to "false". When you "insert" an item \(x\) into the set, you compute the hash value of that element \(h(x)\), and then set the entry at position \(h(x)\) in the hash table to "true". Testing membership of an element \(y\) is then just looking at position \(h(y)\) in the table and seeing whether that table entry is set to "true".

I'm going to ask some questions about this idea as a series of problems. You can turn these in all on the same page, but please number each problem very clearly if you do.

Question 1: What is the worst-case cost of insert and membership-testing in this hash-table-set?