I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), and class of automata that can implement the algorithm. For example is there a range of complexity push down automata can express? If the answer is yes to said question is there a resource depicting the relationship? Thanks!
Relationship of algorithm complexity and automata class
complexity theory;automata;reference request;complexity classes
Yes, there are relationships in many cases!For example, it is known that any language which is accepted by reversal-bounded counter machines are in $P$ (see here).Similarly, we know that all regular languages are in $P$, since there's a polynomial time algorithm for determining if an NFA accepts a given word.There are too many to enumerate here, but in general, more limited computation models are in easier complexity classes.