Performance of Set Implementations
Performance comparison:
| Data Structure |
insert |
delete |
member |
∪, ∩ |
storage |
| unsorted array |
O(n) |
O(n) |
O(n) |
O(n.m) |
O(N) |
| sorted array |
O(n) |
O(n) |
O(log2n) |
O(n+m) |
O(N) |
| unsorted linked list |
O(n) |
O(n) |
O(n) |
O(n.m) |
O(n) |
| sorted linked list |
O(n) |
O(n) |
O(n) |
O(n+m) |
O(n) |
| hash table (lists) |
O(n) |
O(n) |
O(n) |
O(n+m) |
O(n+H) |
| bit-maps |
O(1) |
O(1) |
O(1) |
O(1) |
O(N) |
n,m = #elems, N = max #elems, H = size of hash table
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}