×

# hash table search expected time

 0 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 26●6●8●9 accept rate: 0%

 1 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 4★v_akshay 1.2k●9●16●25 accept rate: 13%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×2,475
×1,664

question asked: 08 Jul '13, 09:46

question was seen: 1,681 times

last updated: 09 Jul '13, 03:35