Runtime complexity of unary languages

Question

I am trying to find a unary language whose runtime complexity is exponential in $n$ (e.g. $\Theta(2^n)$ or a similar expression). But I am not sure how to reason about the runtime of such languages.

I tried the language: $L_1=\{1^{2^k}\}$. This language can be identified by counting the number of ones in the input into a binary register, then checking if the binary register has only zeros and a leading one. This requires $O(n)$ steps to read the input, and probably $O(\log n)$ for each addition, so the total runtime is $O(n \log n)$. Is this correct?

What about the language: $L_2=\{1^{2^{2^k}}\}$? This language can be identified by counting the number of ones in the input into a binary register, then checking if the number of zeros in the register is in $L_1$. This seems like it can be done in time polynomial in $n$.

How can I construct a unary language that can only be identified in exponential time?

Answer 1

Let $L$ be a language in $\mathrm{TIME}(2^{2^n})$ but not in $\mathrm{TIME}(o(2^{2^n}/2^n))$ (such a language exists by the time hierarchy theorem). Define $U = \{1^n : n \in L\}$. Using an algorithm for $L$, we get that $U \in \mathrm{TIME}(2^n + O(n^2))$. Running the same argument backwards, we see that $U \notin \mathrm{TIME}(o(2^n/n))$ (here we use that $O(4^n) \ll 2^{2^n}/2^n$).