# What is the definition of Infinitely Often class in complexity

I was reading a paper and I came across the term $$L\notin i.o.Dtime(2^{n^c}/n^c)$$. What is the meaning of this?

$$L\in DTIME\left(2^{n^c}/n^c\right)$$ if there exists a machine $$M$$ running in time $$O\left(2^{n^c}/n^c\right)$$ which correctly decides membership to $$L$$ for an infinite number of input lengths, i.e. for every $$k\in\mathbb{N}$$ there exists $$n\ge k$$ such that $$\forall x\in\{0,1\}^n : M(x)=\mathbb{1}_{x\in L}$$. You can think of it as having a non trivial special case where we can decide membership to $$L$$ (where by non trivial I mean an infinite set of inputs, not just very short ones).
• I didn't say all input lengths, consider the language $L=\big\{\langle M\rangle | L(M)=\Sigma^* \lor |\langle M \rangle| \text{ is odd}\big\}$ is infinitely often linear, since I can trivially handle odd length inputs, even though $L$ itself is undecidable. Dec 6 '20 at 6:40