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) |
Note: elements for an unordered array with duplicates takes
O(N^{2}) as we have to remove the duplicates.
Note: union for an array with duplicates takes O(N*M) because we
have to recompute the size of the set.