You are not logged in. Please login at to post your questions!


hash table search expected time

why In a hash table in which collisions are resolved by chaining an unsuccessful search and successful search both have same time complexity o(1+@). where @ is a load factor. reply soon

asked 08 Jul '13, 09:46

whiteknight321's gravatar image

accept rate: 0%

Unsuccessful search
O(1) to reach array location, O(@) to traverse the list or to reach the end of the list. (Please note We must reach the end of the list then only we can say that the element was not in the table),
so T(n) = 1+@ where @ = n/m, number of elements/ number of array locations.

Successful search
Assume that new element is inserted at the end of the linked list. Upon insertion of the ith element, the expected length of list is (i-1)/m.
In case of successful search, the expected no. of elements examined is 1 more.
So the time need T(n) = 1/n(∑1<=i<=n(1 + (i-1)/m)
= 1 + n/2m -1/2m
= 1 + @/2 -1/2m = O(1+@)
Comment if you don't get any point of my answer :)


answered 09 Jul '13, 03:32

v_akshay's gravatar image

accept rate: 13%

edited 09 Jul '13, 03:35

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 08 Jul '13, 09:46

question was seen: 1,681 times

last updated: 09 Jul '13, 03:35