We analyze an algorithm that decides whether a given word is a fixed point of a nontrivial morphism. We show that it can be implemented to have complexity in O(m⋅n), where n is the length of the word and m the size of the alphabet.
complexity, fixed points, morphic primitivity
68R15