How much time intersect(A,B) takes?

How much time intersect(A,B) takes?

In my situation both A and B can take values from 1,2,3,...,N only

Answer 1

[Torsten]

Answer from AI:

In MATLAB, the time complexity of the built-in intersect(A, B) function is \(O(N \log N)\), where \(N\) represents the maximum size/length of the input subsets. [1, 2]

Detailed Breakdown

MATLAB’s native implementation does not use hash tables for standard vector sets; instead, it relies on a sort-and-merge (or binary search) approach. Assuming \(\vert{}A\vert{} = n\) and \(\vert{}B\vert{} = m\), where \(n, m \le N\): [1, 2]

• Sorting and Unique-ing (\(O(n \log n + m \log m)\)): MATLAB internally applies a unique sorting mechanism to both input vectors to ensure there are no repetitions and that the values are ordered. This step dominates the runtime and scales at \(O(N \log N)\). [1, 2, 3]
• Comparison/Matching (\(O(n + m)\)): Once both vectors are sorted, MATLAB uses a linear-time comparison helper (ismembc or a two-pointer merge sweep) to identify the common elements. [1, 2]

Combining these steps gives an overall worst-case complexity of \(O(N \log N)\). [1]

Alternative for Dense Subsets

If your subsets are exceptionally dense within the universe \(\{1, 2, \dots, N\}\), you can achieve \(O(N)\) linear time using logical indexing (bitmaps) instead of the default intersect function: [1]

matlab

% O(N) alternative using logical indexing
bitA = false(1, N); bitA(A) = true;
bitB = false(1, N); bitB(B) = true;
C = find(bitA & bitB); 

[Sumit]

It has been epxlianed somewhere in MATLAB documentation?

[Torsten]

Answer from AI:

No, this algorithmic complexity is not officially documented anywhere in the MATLAB documentation.

MathWorks deliberately omits explicit Big-O runtime complexities from the official MATLAB Documentation for core mathematical and set functions like intersect, unique, or setdiff. [1]

Why doesn't MathWorks document it?

• Implementation Flexibility: MathWorks reserves the right to refactor or change the underlying algorithms between MATLAB releases without needing to update specification documentation. For instance, they might switch from a sorting-based method to hash-map implementations for certain data types if it improves performance.
• Hardware Dependability: MATLAB relies heavily on underlying compiled libraries (like BLAS/LAPACK) and hardware-level optimizations (SIMD vectorization, cache sizes, multithreading). Because of this, theoretical Big-O complexities often fail to accurately reflect real-world performance on modern processors. [1]

How do we know the complexity then?

The breakdown provided earlier comes from two reliable developer methods:

1. Source Code Inspection: Many foundational MATLAB functions are written in MATLAB's own language as .m files. If you run edit intersect in your MATLAB Command Window, you can open and read the exact script MathWorks uses. Inside, you can see that the function immediately passes the inputs to unique (which relies on sort), introducing the unavoidable \(\mathcal{O}(N \log N + M \log M)\) bottleneck.
2. Community Profiling: The empirical performance behavior has been widely reverse-engineered, timed, and verified by users on MATLAB Answers and Stack Overflow. [1]