Is it the case that set membership problem for all regular languages can be solved in the time complexity of order $O(n)$ ? And Can we say that all set membership problems that can be solved in $O(n)$ are regular, where n is the input set?
My approach: We can construct a DFA for the regular language, then in that case the time complexity will be of order $O(n)$, but it does not prove that all set membership problems that run in $O(n)$ will be regular so how should we proceed with this part of the proof.