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