Q:

Algorithm analysis, which one is correct?

I'm a programmer, but I've not learned CS, so I've poor understanding of algorithms analysis. I'm reading a book about this theme and I have a question:
Suppose we have a problem: Given two strings, we need to understand is the first string an anagram of the second string.
The first solution that I though was:
def anagram(s1, s2):
    for char in s1:
        if not char in s2:
            return False
    return True

In analysis of such an algorithm, should I care about complexity of this piece of code?
if not char in s2

To be more precise is it important, which algorithm is used in search operation, which will be executed in each iteration of the for loop?

Ps: sorry for misunderstanding, I know that the algorithm is wrong, because an anagram strings should be the same length. But it is not important for now.

A:

First, you analyse the complexity of each line (n, m = len(s1), len(s2) and I will assume n > m):
def anagram(s1, s2):
    for char in s1: # O(n)
        if not char in s2: # O(m)
            return False # O(1)
    return True # O(1)

Note that if not char in s2: is O(m) as, in the worst case, you have to check every character in s2 to be sure char isn't there.
Then you combine; as you have nested operations, the overall complexity is O(n * m). 

As pointed out in the comments, you can significantly improve by noting that membership testing for a set is O(1) (except where every hash collides, see e.g. https://wiki.python.org/moin/TimeComplexity):
def anagram(s1, s2):
    s2 = set(s2) # O(m)
    for char in s1: # O(n)
        if not char in s2: # O(1)
            return False # O(1)
    return True # O(1)

By moving the O(m) operation out of the loop, you reduce the overall complexity to O(n). 
However, this algorithm does not actually determine whether s1 and s2 are anagrams.

If you are looking for an efficient way to actually solve the problem, note that Python's sort ("Timsort") is O(n log n):
def anagram(s1, s2):
    s1 = sorted(s1) # O(n log n)
    s2 = sorted(s2) # O(m log m)
    return s1 == s2 # O(m)

Now you have no nesting, so the total complexity is O(n log n). This is admittedly slower than O(n), but it has the advantage of working.

