CBHTs: analysis
Analysis of the CBHT search/insertion/deletion algorithms (counting comparisons):
Let the number of entries be n.
In the best case, no bucket contains more than (say) 2 entries:
Max. no. of comparisons = 2
Best-case time complexity is O(1).
In the worst case, one bucket contains all n entries:
Max. no. of comparisons = n
Worst-case time complexity is O(n).