I have been given an assignment that I'm having a very hard time understanding.
The assignment is to prove that if an algorithm accepts a non-regular language, the complexity is $\Omega(\log \log n)$ (so if the language is regular, the complexity is $O(\log \log n)$). The computational model to be used is a Turing machine with one input and one work tape.
Here's an excerpt from a book called Theory of computation by Dexter C. Kozen that I will be using to prove the assumption (if it's not allowed to post such an excerpt here please let me know, I'll remove it and share just some parts there instead, I posted it whole as I consider all information there to be important).
I have read this excerpt several times and there are several parts that I wasn't able to grasp. If I understand this correctly, $N$ is equal to all possible configurations (a crossing sequence) for a single cell. On the other hand, $\sum^{m}_{i=0} N^{i}$ is equal to crossing sequences on $m$ cells. So the thing I don't understand about this is why the $n/2$ first (or last) crossing sequences have to be distinct. I suppose I understand that you'd be able to cut a part of the input string if there were two identical crossing sequences on two positions, but I don't see why the number of required distinct crossing sequences equals $n/2$ and not some other number. For example, why do we partition $x$ into 2 parts and not 4 or some other number?
One other thing that I really don't understand is the very last equation, which says "Combining (1.3), (1.4) and (1.5) and taking logs, we get $S(n) \geq \Omega (\log \log n)$." I just don't understand how it's possible to come up with this equation by taking those three mentioned equations. The first step should be replacing $N$ in those equations, which gives me these two equations:
$\frac{n}{2} \leq \sum^{m}_{i=0} (q \cdot S(n)\cdot d^{S(n)})^{i} = \frac{(q \cdot S(n)\cdot d^{S(n)})^{m+1}-1}{(q \cdot S(n)\cdot d^{S(n)})-1}$
$m \leq 2 \cdot (q \cdot S(n)\cdot d^{S(n)})$
I don't know how to combine these two equations and reach the desired equation that is $S(n) \geq \Omega (\log \log n)$. Thank you for any help in advance.