General Remarks on Various Methods
- Ordinary lookup in contiguous tables is superior in both speed
and convenience if it applies, and this is a very big
if.
- Sequential (linear) search is the most flexible method since it
can be used with contiguous or linked storage, and with sorted or
unsorted data.
- Binary search is very fast, but also much more demanding of the
data, since it must be sorted if it is to be kept in contiguous
storage, or, alternatively, placed in tree-structured storage.
But, a binary search tree offers the (quite good, and uniform)
performance of O(log n) for all three of the usual operations:
insert, delete and find.
- Though it can be very fast for all the usual operations (insert,
delete, find), hashing is even more demanding in some respects, since
it is based on a peculiar ordering of some kind for the keys, which may
render it useless for other purposes such as obtaining sorted
data.
| Average Performance Complexity
of the Major Storage-and-Retrieval Approaches |
|---|
|
|
contiguous
unsorted
(vector) |
contiguous
sorted
(vector) |
non-contiguous
unsorted
(linked sequence) |
non-contiguous
sorted
(linked sequence) |
binary search tree
(balanced) |
hash table
(perfect
hash function) |
| insert |
O(1) |
O(n) |
O(1) |
O(n) |
O(log
n) |
O(1) |
| delete |
O(n) |
O(n) |
O(n) |
O(n) |
O(log
n) |
O(1) |
| search/find |
O(n) |
O(log n) |
O(n) |
O(n) |
O(log n) |
O(1) |
overall
performance |
O(n) |
O(n) |
O(n) |
O(n) |
O(log n) |
O(1) |