  We consider online algorithms with respect to the competitive ratio. Here, we
investigate quantum and classical one-way automata with non-constant size of
memory (streaming algorithms) as a model for online algorithms. We construct
problems that can be solved by quantum online streaming algorithms better than
by classical ones in a case of logarithmic or sublogarithmic size of memory.
