The complexity of the optimal algorithm is O(N + M), because the input is not O(N ^ 2) is O(M).