It's O(E+V)
to find a cycle in some parse tree. But that's not the problem. The problem is to
determine whether or not there exist any circularities in any of the parse trees that a given SDD could have to translate. (Emphasis added).
That's a rather more difficult problem.