It is necessary to implement the following verification algorithm: is the set of m integers S a subset of a set T of size n, m <= n, beyond O (n) in the average case From ideas using a hash table as a container containing a larger set. The elements of a set with less power will be checked for compliance with the elements of the hash table. Tell me please, is such an approach possible, is a simpler implementation possible?

  • S and T sets - must be understood, unsorted? - Akina
  • one
    It is possible to hash a smaller set and remove elements from it when iterating over a larger one. True, building a hash or sorting somehow still goes beyond O (n). - Mike

1 answer 1

The expression "for O (n) in the average case" requires decoding.

But if we assume that m log m <= O (n) and n log m = O (n) , then this option meets the requirements for speed:

  1. Sorting the set S.
  2. Binary search of elements of the set T by the ordered set S (matched elements of the set S - mark!)
  3. If all elements of S are marked, then it is a subset of T.