There's a question which is answered at the end of the book, but I have problem understanding the answer, my own understanding is that its lower bound would be $n^2$ as well.
A palindrome is a a binary string that is identical when read in either direction, e.g. 0010100 or 11011011. Describe a DTM that decides the language $L_{PAL} = \{x \in \Sigma^* | \text{x is a > palindrome}\}$.
What lower bounds can you give for the time complexity of any DTM that decides $L_{PAL}$?
Solution: There is an obvious lower bound for the time-complexity of a DTM accepting $L_{PAL}$ on an input of length $n$. In order to recognize that a string is a palindrome the whole string must be examined hence the running time must be at least $n$. (In fact any single tape DTM accepting $L_{PAL}$ must have time-complexity $\Omega(n^2)$.)
I don't understand how could the lower bound be $n $ and not $n^2$.
If $n^2$ is a lower bound, then automatically $n$ is also a lower bound; it just isn’t as tight a lower bound. The lower bound of $n$ is a very crude estimate obtained simply by recognizing that it’s impossible to be sure that a string is a palindrome without seeing the whole string: changing the last symbol of a palindrome gives you a non-palindrome, so the first $n-1$ symbols can’t provide sufficient information. Thus, you have to process every symbol, and the time complexity of doing so is at least $n$ even if you’re doing the same thing with each symbol. A more detailed analysis shows that we can improve this lower bound to $n^2$.