User:Realazthat/Notes/Algorithms/Set-intersection: Difference between revisions

Content added Content deleted

Inline

Revision as of 17:37, 6 January 2011

Set Difference Not Empty

#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

#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 B )
    if ( c in D )
       return true
  
  return false

@@ Line 32: / Line 32: @@
 == Set Intersection Not Empty ==
+<math>O(min(|A|,|B|))</math> assuming set membership testing is constant time.
 <pre>
 #Set Intersection Not Empty