Check if one string is a permutation of another using Python
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 as

for char in first_string:
    count_first[char] = 1 + count_first.get(char, 0)


The epilogue could be simplified to

return count_first == count_other




It pays to get familiar with the standard Python library, though.  Your entire function could be more simply implemented as

from collections import Counter

def 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).