Expected-case Cost | Worst-case Cost | ||
lookup() | O(n) (i.e. some constant times n) | O(n) | |
DictLRS | insert() | O(n) | O(n) |
remove() | O(n) | O(n) | |
lookup() | O(log n) (i.e. some constant times log n) | O(n) | |
DictBT | insert() | O(log n) | O(n) |
remove() | O(log n) | O(n) | |
lookup() | O(log n) | O(log n) | |
DictArray | insert() | O(n) | O(n) |
remove() | O(n) | O(n) | |