Compute the expected running time for a successful search

Reference no: EM131165958

Suppose you hash n items into a hash table of size k. It is natural to ask about the time it takes to find an item in the hash table. We can divide this into two cases, one when the item is not in the hash table (an unsuccessful search), and one when the item is in the hash table (a successful search). Consider first the unsuccessful search. Assume the keys hashing to the same location are stored in a list with the most recent arrival at the beginning of the list. Use our expected list length to bound the expected time for an unsuccessful search. Next consider the successful search. Recall that when we insert items into a hash table, we typically insert them at the beginning of a list, and so the time for a successful search for item i should depend on how many entries were inserted after item

i. Carefully compute the expected running time for a successful search. Assume that the item you are searching for is randomly chosen from among the items already in the table. (Hint: The unsuccessful search should take roughly twice as long as the successful one. Be sure to explain why this is the case.)

Reference no: EM131165958

Questions Cloud

Explain what a deadweight loss is and what causes it : Explain what consumer surplus and producer surplus is and how it can be found. Explain what a deadweight loss is and what causes it. Explain the difference between private goods and public goods

What rule of law applies to the abovementioned issue : What is the basic issue? Include some facts in this section. What rule of law applies to the abovementioned issue? Apply the rule of law to the specific facts of the case.

What do you suggest that brian tell joe : Because Brian has a little inside knowledge about Joe's agenda for this meeting, he has been considering how to handle Joe. What do you suggest that Brian tell Joe?

What is principle-agent problem and how can it be avoided : What is the principle-agent problem and how can it be avoided? What is the difference between explicit and implicit costs? What is the law of diminishing returns

Compute the expected running time for a successful search : Carefully compute the expected running time for a successful search. Assume that the item you are searching for is randomly chosen from among the items already in the table. (Hint: The unsuccessful search should take roughly twice as long as the s..

Evaluate barrys conduct of the observation assignment : I'd better contact Chuck (the director of store management) and let him know what went on here today." Evaluate Barry's conduct of the observation assignment.

What is the expected number of empty slots in hash table : What is the expected number of empty slots when we hash 2k items into a hash table with k slots? What is the expected fraction of empty slots close to when k is reasonably large?

What is the total cost of production : Complete the chart. What is the total cost of production when 2000 toys are produced? What is the variable cost of production when 5000 toys are produced

What suggestions do you have that could have improved : At this point, Anne has just a 14% response rate, which she is sure will not please her team leader. What suggestions do you have that could have improved Anne's response rate to the questionnaire?

User Account

All Pages