| Next | Hash Hash Hash | 21 |
Big drawback of assoc lists:
all operations run in O(n) time
To insert n items into an assoc list takes O(n2) time
(or you can trade time for space)
Totally impractical for large structures
How to fix this?
One answer: use trees
Typical fetch and store time in a tree is O(log n)
But worst-case behavior is O(n) and is very common
| Next | |
21 |