Constant-Working-Space Algorithms: How Fast Can We Solve Problems without Using Any Extra Array?

In this talk I will present a new direction of algorithms which do not use any extra working array. More formally, we want to design efficient algorithms which require no extra array of size depending on input size

n

but use only constant working storage cells (variables), each having

O

(log

n

) bits. As an example, consider a problem of finding the median among

n

given numbers. A linear-time algorithm for the problem is well known. An ordinary implementation of the algorithm requires another array of the same size. It is not very hard to implement the algorithm without using any additional array, in other words, to design an in-place algorithm. Unfortunately, it is

not

a constant working space algorithm in our model since it requires some space, say

O

(log

n

) space, for maintaining recursive calls. A good news is that an efficient algorithm is known which finds the median in

O

(

n

1 + 

ε

) time using

O

(1/

ε

) working space for any small positive constant

ε

. The algorithm finds the median without altering any element of an input array. In other words, the input array is considered as a read-only array.