Running Time Analysis of a Simple Binary Search Algorithm
Sorting the big set takes time $O(n\log n)$. You perform $m$ binary searches, each taking $O(\log n)$, for a total of $O(m\log n)$ time spent on binary search. The total running time of the algorithm is thus
$$
O(n\log n + m\log n) = O((n + m)\log n) = O(n\log n),
$$
assuming $m \leq n$.

Note that it is even better to sort the smaller list, since then the running time improves to $O(n\log m)$.