The code below is an attempt at a solution to an exercise from the book Cracking the Coding Interview.  I believe that the worst case time complexity of the code below is \$O(n)\$, where n is the length of each string (they should be the same length since I am checking if there lengths are equal) and the space complexity is \$O(n)\$. Is this correct?  In particular does checking the length of each string take \$O(1)\$ time?def is_permutation(first_string, other_string):    if len(first_string) != len(other_string):        return False    count_first = {}    count_other = {}    for char in first_string:        if char in count_first.keys():            count_first[char] += 1        else:            count_first[char] = 1    for char in other_string:        if char in count_other.keys():            count_other[char] += 1        else:            count_other[char] = 1    for char in count_first.keys():        if char not in count_other.keys():            return False        elif count_first[char] != count_other[char]:            return False    return True
Check if one string is a permutation of another using Python
python;strings;python 3.x;complexity
Yes, len(str) should be O(1) in Python.  (Good question!)  Each of your for loops is O(n), so your whole function is O(n).Your counting loops could be written more compactly asfor char in first_string:    count_first[char] = 1 + count_first.get(char, 0)The epilogue could be simplified toreturn count_first == count_otherIt pays to get familiar with the standard Python library, though.  Your entire function could be more simply implemented asfrom collections import Counterdef is_permutation(a, b):    return len(a) == len(b) and Counter(a) == Counter(b) where len(a) == len(b) is an optional optimization.  Writing less code simplifies maintenance and tends to create fewer opportunities for introducing bugs (as in Rev 2 of your question).