In the (only) implementation of XCTAssertUnorderedEqualSequences (where elements are Equatable), it converts the sequence into an Array. Then it iterates through the second sequence, calling firstIndex(of:) on the first array (O(n)), which totals to O(n2). If a Set were used (when the elements are Hashable), then getting the index of an element is O(1), which would make the total algorithmic complexity O(n).
Expected behavior
XCTAssertUnorderedEqualSequences is O(n) when Element: Hashable
Actual behavior
XCTAssertUnorderedEqualSequences is O(n2) when Element: Hashable
mdznr
commented
2 years ago
In the (only) implementation of
XCTAssertUnorderedEqualSequences(where elements areEquatable), it converts the sequence into anArray. Then it iterates through the second sequence, callingfirstIndex(of:)on the first array (O(n)), which totals to O(n2). If aSetwere used (when the elements areHashable), then getting the index of an element is O(1), which would make the total algorithmic complexity O(n).Expected behavior
XCTAssertUnorderedEqualSequencesis O(n) whenElement: HashableActual behavior
XCTAssertUnorderedEqualSequencesis O(n2) whenElement: Hashable