why is this o(n) three-way set disjointness algorithm slower than then o(n^3) version?
<p>O(n) because converting list to set is O(n) time, getting intersection is O(n) time and len is O(n)</p>

<pre><code>def disjoint3c(A, B, C):
    """Return True if there is no element common to all three lists."""
    return len(set(A) &amp; set(B) &amp; set(C)) == 0
</code></pre>

<p>or similarly, should be clearly O(N)</p>

<pre><code>def set_disjoint_medium (a, b, c):
    a, b, c = set(a), set(b), set(c)
    for elem in a:
        if elem in b and elem in c:
            return False
    return True
</code></pre>

<p>yet this O(n^3) code:</p>

<pre><code>def set_disjoint_slowest (a, b, c):
    for e1 in a:
        for e2 in b:
            for e3 in c:
                if e1 == e2 == e3:
                    return False
    return True
</code></pre>

<p>runs faster</p>

<p>see time where algorithm one is the n^3, and algorithm three is the O(n) set code... algorithm two is actually n^2 where we optimize algorithm one by checking for disjointness before the third loop starts</p>

<pre><code>Size Input (n):  10000

Algorithm One: 0.014993906021118164

Algorithm Two: 0.013481855392456055

Algorithm Three: 0.01955580711364746

Size Input (n):  100000

Algorithm One: 0.15916991233825684

Algorithm Two: 0.1279449462890625

Algorithm Three: 0.18677806854248047

Size Input (n):  1000000

Algorithm One: 1.581618070602417

Algorithm Two: 1.146049976348877

Algorithm Three: 1.8179030418395996
</code></pre>

<p>O notation ignores all the constant factors. So it will only answer for <em>infinite</em> data sets. For any finite set, it is only a rule of thumb.</p>

<p>With interpreted languages such as Python and R, constant factors can be pretty large. They need to create and collect many objects, which is all O(1) but not free. So it is fairly common to see 100x performance differences of virtually equivalent code, unfortunately.</p>

<p>Secondly, the first algorithm computes <em>all</em> common elements, while the others fail on the <em>first</em>. If you benchmark <code>algX(a,a,a)</code> (yes, all three sets be the same) then it will do much more work than the others!</p>

<p>I would not be surprised to see a sort-based O(n log n) algorithm to be very competitive (because sorting is usually incredibly well optimized). For integers, I would use numpy arrays, and by avoiding the python interpreter as much as possible you can get very fast. While numpys <code>in1d</code> and <code>intersect</code> will likely give you aan O(n^2) or O(n^3) algorithm, they may end up being faster as long as your sets are usually disjoint.</p>

<p>Also note that in your case, the sets won't necessarily be pairwise disjoint... <code>algX(set(),a,a)==True</code>.</p>

python algorithm complexity-theory