b. You are given an application that matches words from song lyrics to song titles. The current system uses a hash table implementation. Each song title is hashed to an entry in the table and each entry would then point to a linked list that contained references to every word in that song's lyrics. Assume that the database has A distinct words and B songs that have been hashed.

i. (3 points) Assuming no collisions in the hash table, what is the worst-case complexity for a method that will print ALL the titles of the songs that contain a particular word? Give the answer in big-O notation in terms of A and/or B.

ii. (3 points) Assuming no collisions in the hash table, what is the worst-case complexity of a method that returns true if a particular word is in a particular song? Give the answer in big-O notation in terms of A and/or B.

iii. (3 points) How does the answer to part ii change if the words are stored using a binary search tree rather than a linked list?

Transcribed Image Text:

The following hash table uses quadratic probing with f(i) = 1². Fill in the table by inserting the following integer keys in order using the hash function hash(x) = x %11. Do not rehash, simply put the numbers in their correct boxes. 32, 10, 17, 9, 20, 33, 66 NOTE: YOU MUST GIVE AN ENTRY FOR EACH BOX. For boxes with a value in it just type the number itself. For boxes that are empty type just the character X 0 1 2 32. st 4 in 5 6 7 00 9 10 The following hash table uses quadratic probing with f(i) = 1². Fill in the table by inserting the following integer keys in order using the hash function hash(x) = x %11. Do not rehash, simply put the numbers in their correct boxes. 32, 10, 17, 9, 20, 33, 66 NOTE: YOU MUST GIVE AN ENTRY FOR EACH BOX. For boxes with a value in it just type the number itself. For boxes that are empty type just the character X 0 1 2 32. st 4 in 5 6 7 00 9 10

Answer rating: 100% (QA)

i Answer The worstcase complexity is OA B This is because you would have to iterate through all of t... View the full answer