I am trying to show that given a co-finite language $A$, $A \in \text{TIME}(1)$.
If $A$ is co-finite, $A$ is regular, so $A \in \text{TIME}(n)$.
I'm not sure how to proceed from here. Any hints?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityI am trying to show that given a co-finite language $A$, $A \in \text{TIME}(1)$.
If $A$ is co-finite, $A$ is regular, so $A \in \text{TIME}(n)$.
I'm not sure how to proceed from here. Any hints?
Your observation that co-finite languages are regular and hence in linear time is absolutely correct. Unfortunately, it's not enough, since there are definitely regular languages that require linear, and not constant, time (e.g., even checking if your input matches $0^*$ requires you to look at the whole input, unless $\Sigma=\{0\}$).
There are only finitely many strings not in a co-finite language. So, how much input do you need to read before you know whether the input is one of those?