**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%