I understand the notion of crossing sequences when talking about time, however how are they used to actually prove strict lower bounds for some decision/search problems?
For example, suppose that you have an array of size N and you want to find the maximum number in it.
Speaking informally, we need at least a pointer to run through the input and some other variable to update whenever we find a number in the input tape that is bigger than the temporary number in our work tape, thus leading us to use Ω(logn) space.
However, how can you prove that you can't do it in O(1) space? Many articles online are using crossing sequences for proving space lower bounds, but they don't show how to do it, they just say something along the lines of "using crossing sequences it's trivial to show that the space lower bound is ..."
which isn't very helpful for beginners like me. Thanks!