Consider two English documents D1 and D2; denoted by S(D1) and
S(D2) as the sets of English words in them, respectively, where each word has O(1) length, i.e.,
each word consists of only a constant number of characters.
The similarity between D1 and D2 is defined as the Jaccard Similarity between the sets of words
in them, i.e., S(D1) and S(D2). Specifically, the similarity between D1 and D2 is computed as:
Sim(D1, D2) = |S(D1) ∩ S(D2)|/
|S(D1) ∪ S(D2)| .
For simplicity, we assume that the sets of words in D1 and D2 have the same size, namely, |S(D1)| =
|S(D2)|. And we let n = |S(D1)| = |S(D2)|.
Design an algorithm to compute Sim(D1, D2) in O(n) expected time. You will need to justify
the time complexity of your algorithm with appropriate analysis.  Provide your response in exactly 3 paragraphs (separated nearby paragraphs with 3 aterisk symbols ***).
user