[Lecture Summary] 04 Algorithm and Data Structure : Hashing

This contents is based on Lecture of link

Comparison Model

Return value for comparison is binary.

Then we can apply comparison for set interface to support (static) find operation!
At this moment, all we need to do is count comparision which is time complexity!

This can be considered as decision (binary) tree. Leaves are items of set and a “none” case to support non-exist key.

Properties

• # of leaves is (# of items + 1).
• # of comparison becomes the longest path from root to leaf.
• minimum height of tree is $\theta(\log(n))$