b. You are given an application that matches words from song lyrics to song titles. The current
Question:
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?
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest