Anonymous user
User:Realazthat/Notes/Algorithms/Set-intersection: Difference between revisions
User:Realazthat/Notes/Algorithms/Set-intersection (view source)
Revision as of 20:13, 21 January 2011
, 13 years ago→Set Intersection Not Empty
(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:
==
Complexity: O(1) if |A| > |B|, O(|A|) otherwise; assuming O(1) for membership testing.
<pre>
#
if |A| > |B|
return true
Line 13:
return false
</pre>
Complexity: O(1) if |A| > |B|, O(|B|) otherwise.
<pre>
#
if |A| > |B|
return true
Line 29:
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>
| |||