jaredec18

Untitled

Sep 15th, 2019
151
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.64 KB | None | 0 0
  1. Solution:
  2.  
  3. 1)
  4.  
  5. k=N, this means that the number of items is same as the number of slots in the table, so if the hash function is efficient there won't be any collision and chaining won't even be required.
  6.  
  7. 2)
  8.  
  9. No, it is not necessary that k<N, because it provides us an opportunity to fill the complete table.
  10.  
  11. 3)
  12.  
  13. Average number of items = k/N
  14.  
  15. 4)
  16.  
  17. In the worst case all the items will be placed in a single bucket chained to one another.
  18.  
  19. in that case k items.
  20.  
  21. 5)
  22.  
  23. If k>N, it is very much possible that the buckets are left empty.
  24.  
  25. 6)
  26.  
  27. After resizing the table to place the elements in the new table the running time will be O(k).
Advertisement
Add Comment
Please, Sign In to add comment