## ← Keywords and Buckets Solution - Intro to Computer Science

• 2 Followers
• 47 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=0k-hAMfA5uY" data-team="udacity"></div> ``` 2 Languages

Showing Revision 6 created 05/24/2016 by Udacity Robot.

1. So there are two correct answers, the third one, and
2. the fifth one. And this is why a hash table is such a great
3. advance over the linear index, is that we can double the number of keywords, and
4. double the number of buckets, and the look up
5. time stays the same. With the linear index, if we
6. double the number of keywords for each look up, we
7. need to go through the loop once for each keyword.
8. If the keyword was near the end or one that wasn't
9. in the table, the time to look up the keyword would
10. double as we double the number of keywords. With a hash
11. table if we also double the number of buckets when we double
12. the number of keywords, well then the number of keywords in
13. each bucket stays the same. We're dividing the keywords evenly between
14. buckets. So this is the number, the number of keywords per
15. bucket is the number of keywords divided by the number of buckets.
16. Of we double both, that number stays approximately the same. The
17. time to look up only depends on the number of keywords per
18. bucket. The time to find the bucket is very fast, right? We
19. just need to run the hash function, find that element of the
20. list. Both of those don't depend on the size of the
21. list, how long it takes to do that. And then we have
22. to look through the bucket, the size of the bucket, we have
23. to look though each element in the bucket one at a time.
24. So if we keep the number of key words per bucket
25. the same, the look up time stays essentially the same. So that's
26. the great property that hash tables have. If we double the
27. number of buckets, as we double the number of keywords, the expected
28. look up time doesn't change. For the other possibilities, well if
29. we double the number of keywords and keep the same number of
30. buckets, that's going to get slower because the number of keywords
31. per bucket will approximately double. So it's going to take about twice
32. as long for each look up. If we keep the same
33. number of keywords, but double the number of buckets, well then it's
34. going to actually get faster. We'll have the same number of keywords, double
35. the number of buckets. So, this value will be approximately half of
36. what it was before. The expected lookup time will be about
37. half of what is before we doubled the number of buckets. If
38. we have the number of keywords keeping the same number of buckets,
39. well that has essentially the same affect. The average number of keywords
40. per bucket will be half of what it
41. was before, so the expected lookup time will be
42. about half of what it was. And finally
43. if we have both, well that's going to keep
44. the ratio the same so the expected look
45. up time will be about the same. So that's
46. why these two are the correct answers, that those
47. are expected to leave the lookup time essentially unchanged.