Worst-case running time of the array-based implementation of a set where the elements in the array are ordered (unordered) and where the array contains (no) duplicates:
ord. | unord. | ord. | unord. | |
no dupl. | dupl. | dupl. | no dupl. | |
size | O(1) | O(1) | O(1) | O(1) |
isEmpty | O(1) | O(1) | O(1) | O(1) |
isMember | O(log(n)) | O(N) | O(log(N)) | O(n) |
elements | O(n) | O(N^{2}) | O(N) | O(n) |
insertElement | O(n) | O(1) | O(N) | O(n) |
union | O(n+m) | O(N+M) | O(N+M) | O(n*m) |