The creation of a set from an array of n
elements takes O(n)
time complexity. Let us think that the first array is of length n
and the second array is of length m
.
Then the final time complexity of the above implementation would be O(m+n)
. Let us explain this step-by-step:
- We create a set from the first array:
O(n)
. - We traverse through the second array with
filter
method which takesO(m)
. In this traversal process, we check if that element exists in the set from the first array which takesO(1)
. - Finally we create the resulting array from the filtered second array which takes
O(m)
worst time. Remember, although we may return an array, it is crucial to building a set first. The reason is to remove duplicates from the filter of the second array.
So, the final time complexity is O(n + m + m)
= O(m+n)
.