avl tree - AVL vs Hashtable with Chaining -


i know best case , worst case avl tree logn find, insert, , delete. best case , worst case hashtable chaining? how differentiate 2 if given 2 mystery data structures?

what best case , worst case hashtable chaining?

find, insert, delete operation best time o(1) or constant time. worst time,

  • insert: o(1), assuming chaining done adding end of chain
  • delete: o(k), k = number of elements on longest chain. k == n when hashing function poor , n values map same entry , gets chained. so, absolute worst case o(n).
  • find: o(n), using same reasoning delete

how differentiate 2 if given 2 mystery data structures?

just idea:

  • insert data in both structures , plot insertion time insertion operation vs n. choose data make mimic worst case avl tree (i.e. if integers, insert in order 1000000, 99999, 999998...) not hashtable.
  • notice plot being generate. avl tree 1 have insertion time log(n) beginning while should constant hashtable. around 1000th insertion alv tree take 10 times longer insertion (assuming worst case insertion happening). insertion time should same before hashtable. assuming hashtable has enough capacity , hashing function not silly enough conflicts sequential data '1000000, 99999, 999998...'
  • if still not sure, bombard both structure insertion, hoping fill hashtable , force start chaining. after many insertions, notice plots. avl still maintain log(n) curve, hashtable show different curve, like: constant time higher constant value.

Comments

Popular posts from this blog

PHPMotion implementation - URL based videos (Hosted on separate location) -

javascript - Using Windows Media Player as video fallback for video tag -

c# - Unity IoC Lifetime per HttpRequest for UserStore -