Decrease the cost of two lists comparisons
<p>I want to minimize the cost of comparisons of two lists that have some words. In the code below <code>A</code> has 4 words whereas <code>B</code> has 2 words and the cost is <code>O(n^2)</code> that is too bad. While for 100 words it can be time consuming. Can I minimize it somehow?</p>

<pre><code>A= ["helry", "john" , "kat" , "david"]
d="Helry David"
B = d.lower().split()

for x in range(len(A)):
            for i in range(len(B)):
                if A[x] == B[i]:
                    print("Match = " + A[x])
                else:
                    print("No")
</code></pre>

<p>Use sets instead of lists (btw these are not called arrays in Python). What you want is the intersection of two sets, which is (on average) <code>O(min(len(A), len(B))</code> (<a href="https://wiki.python.org/moin/TimeComplexity" rel="nofollow">https://wiki.python.org/moin/TimeComplexity</a>). And since this algorithm is built-in and implemented in C, it is much faster than anything you could write in Python code.</p>

<p>Example (A and B are considered to be defined as before):</p>

<pre><code>&gt;&gt;&gt; set(A) &amp; set(B)
{'david', 'helry'}
</code></pre>

<p>This gives you a set of all values that are contained in both A and B.</p>

python time-complexity