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

  • 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