Time complexity of the algorithm

[Eli-Black-Work]

Would you be okay with adding something to the README stating what the time complexity of the algorithm is? My understanding from looking at the code is that it's O(n log n), but I'm not sure if that's correct.

Thanks :)

[sindresorhus]

Happy to document it, but I don't know the answer.

[Eli-Black-Work]

Haha, okay, got it. Well, hopefully someone else who is algorithmically inclined will come along and see this :)

[wilsonwangme]

Haha, okay, got it. Well, hopefully someone else who is algorithmically inclined will come along and see this :)

If arrayOne's length is a and arrayTwo's length is b, isn't it the time complexity is O(ab)?

1. We need at least iterate arrayOne a times and generally iterate arrayTwo b/2 times as an average situation.
2. The iteration of arrayTwo is in each arrayOne's iteration, so the time complexity is O(a * b/2).
3. The constant level factor should be ignored.
4. As a result, the answer is O(ab)

[dotlambda]

If you call arrayDiffer(a, b) and m = a.length, n = b.length, then turning b into a set takes O(n * log n) because inserting a single element into the set takes O(n), and filtering a takes O(m * log n). To summarize, the complexity is O(max(m, n) * log n). But that's a worst-case analysis which might be irrelevant in real life.