[Solved]: Is every linear-time algorithm a streaming algorithm?

Problem Detail: 

Over at this question about inversion counting, I found a paper that proves a lower bound on space complexity for all (exact) streaming algorithms. I have claimed that this bound extends to all linear time algorithms. This is a bit bold as in general, a linear time algorithm can jump around at will (random access) which a streaming algorithm can not; it has to investigate the elements in order. I may perform multiple passes, but only constantly many (for linear runtime).

Therefore my question:

Can every linear-time algorithm be expressed as a streaming algorithm with constantly many passes?

Random access seems to prevent a (simple) construction proving a positive answer, but I have not been able to come up with a counter example either.

Depending on the machine model, random access may not even be an issue, runtime-wise. I would be interested in answers for these models:

• Turing machine, flat input
• RAM, input as array
• RAM, input as linked list

Asked By : Raphael

Answered By : Tsuyoshi Ito

For streaming algorithms to be meaningful, they have to work with significantly smaller amount of work space than the input itself. For example, if you allow the same amount of work space as the input, then you can trivially state any algorithm as a "single-pass streaming algorithm" which first copies the input to the work space in single pass and then only use the work space.

I think that it is typical to restrict the work space to at most polylogarithmic in the input size when talking about streaming algorithms. Under this assumption, median selection does not have an O(1)-pass streaming algorithm by the result of Munro and Paterson [MP80]: any P-pass streaming algorithm for median selection on N elements has to store Ω(N^1/P) elements. On the other hand, median selection has a well-known deterministic linear-time algorithm [BFPRT73].

[BFPRT73] Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7(4):448–461, Aug. 1973. DOI: 10.1016/S0022-0000(73)80033-9

[MP80] J. Ian Munro and Mike S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, 12(3):315–323, Nov. 1980. DOI: 10.1016/0304-3975(80)90061-4

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3214