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

From Rosetta Code
Content added Content deleted
(Created page with "== Intersection Not Empty == <pre> #Intersection Not Empty INE(A,B): if |A| > |B| return true for ( a in A ) if ( a not in B ) return true return fals...")
 
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Intersection Not Empty ==
== Set Difference Not Empty ==



Complexity: O(1) if |A| > |B|, O(|A|) otherwise; assuming O(1) for membership testing.
<pre>
<pre>
#Intersection Not Empty
#Set Difference Not Empty
INE(A,B):
DNE(A,B):
if |A| > |B|
if |A| > |B|
return true
return true
Line 13: Line 13:
return false
return false

</pre>
</pre>


Complexity: O(1) if |A| > |B|, O(|B|) otherwise.
<pre>
<pre>
#Intersection Not Empty
#Set Difference Not Empty
INE(A,B):
DNE(A,B):
if |A| > |B|
if |A| > |B|
return true
return true
Line 29: Line 29:
return false
return false
</pre>



== Set Intersection Not Empty ==

<math>O(min(|A|,|B|))</math> assuming set membership testing is constant time.
<pre>
#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
</pre>
</pre>

Latest revision as of 20:13, 21 January 2011

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

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
Retrieved from "https://rosettacode.org/wiki/User:Realazthat/Notes/Algorithms/Set-intersection?oldid=169349"