User:Realazthat/Notes/Algorithms/Set-intersection

Set Difference Not Empty

Complexity: O(1) if |A| > |B|, O(|A|) otherwise; assuming O(1) for membership testing.

#Set Difference Not Empty
DNE(A,B):
  if |A| > |B|
    return true
  
  for ( a in A )
    if ( a not in B )
      return true
  
  return false

Complexity: O(1) if |A| > |B|, O(|B|) otherwise.

#Set Difference Not Empty
DNE(A,B):
  if |A| > |B|
    return true
  
  for ( b in B )
    remove b from A
    remove b from B
    if |A| > |B|
      return true
  
  return false

Set Intersection Not Empty

$O(min(|A|,|B|))$ assuming set membership testing is constant time.

#Set Intersection Not Empty
INE(A,B):
  C = |A| < |B| ? A : B
  D = |A| < |B| ? B : A
  
  for ( c in C )
    if ( c in D )
       return true
  
  return false