CS240 Lecture Notes - Avl Tree, Feta, Quicksort
16 Oct 2011
School
Department
Course
Professor
Document Summary
A list is searched to the end of the list. By uniform hashing assumption x is equally likely to be hashed to any of the m buckets, and therefore the expected time to search unsuccessfully for x is the expected length of a list which is alfa. Hence an unsuccessful search has expected time. , kn are the n keys in the hash table and they wereinserted in that order. Computing the hash value h(x) takes equal(1). A list t[h(x)] is searched to the position where x lies. Since elements are inserted at the front of the list, in search for x = ki , we look at those of ki+1, . , kn which are hashed to the same bucketas x. The expected number of these is (n i )/m. Therefore, the expected length of search is.
