1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

A deterministic algorithm running in space $S$ runs in time $\exp S$. If you don't go over the entire array then you don't know the maximum number (formally speaking, consider two arrays differing in the last element, in only one of which it is the maximum). It takes time $n$ to go over the entire array. So $S = \Omega(\log n)$.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Is the first statement proved with crossing sequences? $\endgroup$ – jsguy Sep 21 '14 at 15:24
  • $\begingroup$ No, it's proved using the pigeonhole principle. $\endgroup$ – Yuval Filmus Sep 21 '14 at 15:25
  • $\begingroup$ Would it be possible to apply crossing sequences to prove the same in the problem of finding a maximum of an array? $\endgroup$ – jsguy Sep 21 '14 at 16:34
  • $\begingroup$ There is no need to use a crossing sequence argument, since it is necessary and sufficient to cross any point once. Crossing sequences are useful when the machine actually has to cross over and over again. $\endgroup$ – Yuval Filmus Sep 21 '14 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.