1
$\begingroup$

I'm stuck with the following problem by Skiena (The Algorithm Design Manual, p. 106):

Problem: Give an efficient algorithm to determine whether two sets (of size $m$ and $n$, respectively) are disjoint. Analyze the worst-case complexity in terms of $m$ and $n$, considering the case where $m$ is substantially smaller than $n$.

Solution: First sort the big set – The big set can be sorted in $O(n\log n)$ time. We can now do a binary search with each of the m elements in the second, looking to see if it exists in the big set. The total time will be $O((n + m)\log n)$.

My question: Why is the running time $O((n + m)\log n)$? I would have to perform m binary searches in total (one binary search for every element in $m$) - as one binary search has a running time of $O(\log n)$, I would have to perform $m \cdot \log n$ operations in the worst case. How does this - if at all - translate into $O((n + m)\log n)$?

$\endgroup$
2
  • 1
    $\begingroup$ It takes $O(n\log n)$ to sort the bigger set, and to $O(m\log n)$ to do the binary search, for a total of $O(n\log n + m\log n) = O((m+n)\log n)$. Note that you can do even better if you sort the smaller set instead, replacing $\log n$ with $\log m$. $\endgroup$ – Yuval Filmus May 27 '20 at 18:07
  • $\begingroup$ Thanks, I got it know! $\endgroup$ – Moritz Wolff May 28 '20 at 9:44
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.