Space-Efficient Algorithms for Longest Increasing Subsequence
Masashi Kiyomi Hirotaka Ono Yota Otachi Pascal Schweitzer Jun Tarui
cs.DS


[
    Min Wang
    empty
============




Given a sequence of integers, we want to find a longest increasing subsequence of the sequence.
It is known that this problem can be solved in O(n log n) time and space.
Our goal in this paper is to reduce the space consumption while keeping the time complexity small.
For √(n)≤ s ≤ n, we present algorithms that use O(s log n) bits and 
O(1/s· n^2·log n) time for computing the length of a longest increasing subsequence,
and O(1/s· n^2·log^2 n) time for finding an actual subsequence.

We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors
in the framework of sequential access algorithms with the prescribed amount of space.









§ INTRODUCTION


Given a sequence of integers (possibly with repetitions),
the problem of finding a longest increasing subsequence (LIS, for short) is 
a classic problem in computer science which has many application areas including bioinfomatics and physics
(see <cit.> and the references therein).

It is known that LIS admits an O(n log n)-time algorithm that uses
O(n log n) bits of working space <cit.>,
where n is the length of the sequence.

A wide-spread algorithm achieving these bounds is , devised by Mallows <cit.>.
Given a sequence of length n,  partitions
the elements of the sequence into so-called piles.
It can be shown that the number of piles coincides with the length of a longest increasing subsequence
(see Section <ref> for details).
Combinatorial and statistical properties of the piles in  are well studied 
(see <cit.>).



However, with the dramatic increase of the typical data sizes in applications over the last decade, a main memory consumption in the order of Θ(n log n) bits is excessive in many algorithmic contexts, especially for basic subroutines such as LIS.
We therefore investigate the existence of space-efficient algorithms for LIS.





    Our results


In this paper, we present the first space-efficient algorithms for LIS that are exact.

We start by observing that
when the input is restricted to permutations, an algorithm using O(n) bits can be obtained
straightforwardly by modifying a previously known algorithm (see Section <ref>).
Next, we observe that a Savitch type algorithm <cit.> for this problem uses 
O(log^2 n) bits and thus runs in quasipolynomial time.
However, we are mainly interested in space-efficient algorithms that also behave well with regard to running time.
To this end we develop an algorithm that determines the length of a longest increasing subsequence using O(√(n)log n) bits which runs in O(n^1.5log n) time. Since the constants hidden in the O-notation are negligible, 
the algorithm, when executed in the main memory of a standard computer, may handle a peta-byte input on external storage.


More versatile, in fact, our space-efficient algorithm is memory-adjustable 
in the following sense. (See <cit.> for information on memory-adjustable algorithms.)
When a memory bound s with √(n)≤ s ≤ n is given to the algorithm, it computes with O(s log n) bits of working space 
in O(1/s· n^2log n) time the length of a longest increasing subsequence.

When s = n our algorithm is equivalent to the previously known algorithms mentioned above.
When s = √(n) it uses, as claimed above, O(√(n)log n) bits and runs in O(n^1.5log n) time.


The algorithm only determines the length of a longest increasing subsequence. 
To actually find such a longest increasing subsequence, one can run the length-determining algorithm n times to successively construct the sought-after subsequence. 
This would give us a running time of O(1/s· n^3log n). However, we show that one can do much better, achieving a running time of O(1/s· n^2log^2 n) 
without any increase in space complexity,
by recursively finding a near-mid element of a longest increasing subsequence.



To design the algorithms, we study the structure of the piles arising in  in depth and show that
maintaining certain information regarding the piles suffices to simulate the algorithm. 
Roughly speaking, our algorithm divides the execution of  into O(n/s) phases,
and in each phase it computes in O(n log n) time information on the next O(s) piles, while forgetting previous information.

Finally, we complement our algorithm with a lower bound in a restricted computational model. 

In the sequential access model, an algorithm can access the input only sequentially.
We also consider further restricted algorithms in the multi-pass model,
where an algorithm has to read the input sequentially from left to right
and can repeat this multiple (not necessarily a constant number of) times.

Our algorithm for the length works within the multi-pass model,
while the one for finding a subsequence is a sequential access algorithm.
Such algorithms are useful when large data is placed in an external storage
that supports efficient sequential access.
We show that the time complexity of our algorithms
is optimal up to polylogarithmic factors in these models.





    Related work

The problem of finding a longest increasing subsequence (LIS) is 
among the most basic algorithmic problems on integer arrays and has been studied continuously since the early
1960's.

It is known that LIS can be solved in O(n log n) time and space <cit.>,
and that any comparison-based algorithm needs Ω(n log n) comparisons
even for computing the length of a longest increasing subsequence <cit.>.

For the special case of LIS where the input is restricted to permutations,
there are O(n loglog n)-time algorithms <cit.>.

, an efficient algorithm for LIS, has been a research topic
in itself, especially in the context of Young tableaux <cit.>.

Recently, LIS has been studied intensively in the data-streaming model,
where the input can be read only once (or a constant number of times) sequentially from left to right.
This line of research was initiated by Liben-Nowell, Vee, and Zhu <cit.>,
who presented an exact one-pass algorithm and a lower bound for such algorithms.
Their results were then improved and extended by many other groups <cit.>.

These results give a deep understanding on streaming algorithms with a constant number of passes
even under the settings with randomization and approximation.
(For details on these models,
see the very recent paper by Saks and Seshadhri <cit.> and the references therein.)

On the other hand, multi-pass algorithms with a non-constant number of passes have not been studied for LIS.

While space-limited algorithms on both RAM and multi-pass models
for basic problems have been studied since the early stage of algorithm theory,
research in this field has recently intensified.
Besides LIS, other frequently studied problems include sorting and 
selection <cit.>,
graph searching <cit.>, 
geometric computation <cit.>, and
k-SUM <cit.>.








§ PRELIMINARIES



Let = (1),(2),…,(n) be a sequence of n integers possibly with repetitions.
For 1 ≤ i_1 < … < i_ℓ≤ n,
the subsequence i_1, …, i_ℓ of 
is the sequence (i_1), …, (i_ℓ).
A subsequence i_1, …, i_ℓ is an increasing subsequence of 
if (i_1) < … < (i_ℓ). 

If (i_1) ≤…≤(i_ℓ), then the sequence  is non-decreasing.
We analogously define decreasing subsequences and non-increasing subsequences.

By (), we denote the length of a longest increasing subsequence of .

For example, consider a sequence _1 = 2, 8, 4, 9, 5, 1, 7, 6, 3.
It has an increasing subsequence _11,3,5,8 = 2, 4, 5, 6.
Since there is no increasing subsequence of _1 with length 5 or more, we have (_1) = 4.

In the computational model in this paper, we use the RAM model with the following restrictions that are standard in the context of sublinear space algorithms.
The input is in a read-only memory and the output must be produced on a write-only memory.
We can use an additional memory that is readable and writable.
Our goal is to minimize the size of the additional memory
while keeping the running time fast.
We measure space consumption in the number of bits used (instead of words)
within the additional memory.









§ 



Since our algorithms are based on the classic ,
we start by describing it in detail and recalling some important properties regarding its internal configurations.

Internally, the algorithm maintains a collection of piles.
A pile is a stack of integers.
It is equipped with the procedures push and top:
the push procedure appends a new element to become the new top of the pile; and
the top procedure simply returns the element on top of the pile, which is always the one that was added last.

We describe how  computes ().
See Algorithm <ref>.
The algorithm scans the input  from left to right (Line <ref>).
It tries to push each newly read element (i) to a pile with a top element larger than or equal to (i).
If on the one hand there is no such a pile,  creates a new pile to which it pushes (i) (Line <ref>).
On the other hand, if at least one such pile exists,  pushes (i) to the oldest pile that satisfies the property (Line <ref>).
After the scan, the number of piles is the output, which happens to be equal to () (Line <ref>).



We return to the sequence _1 = 2, 8, 4, 9, 5, 1, 7, 6, 3 for an example.
The following illustration shows the execution of Algorithm <ref> on _1. In each step the bold number is the newly added element.
The colored (and underlined) elements in the final piles form a longest increasing subsequence _11,3,5,8 = 2, 4, 5, 6,
which can be extracted as described below.




  =0.5mm
  
    

    

    2 

    P_1
  
  
    

       

    2     8 

    P_1     P_2
  
  
    

        4 

    2     8 

    P_1     P_2
  
  
    

          4     

    2     8     9 

    P_1     P_2     P_3
  
  
    

          4     5 

    2     8     9 

    P_1     P_2     P_3
  
  
    

    1     4     5 

    2     8     9 

    P_1     P_2     P_3
  
  
    

    1     4     5     

    2     8     9     7 

    P_1     P_2     P_3     P_4
  
  
    

    1     4     5     6 

    2     8     9     7 

    P_1     P_2     P_3     P_4
  
  
          3             

    1     4     5     6 

    2     8     9     7 

    P_1     P_2     P_3     P_4
  




Given a sequence  of length n,
 computes () in O(n log n) time using O(n log n) bits of working space.





 §.§ Correctness of 

It is observed in <cit.> that
when the input is a permutation π,
the elements of each pile form a decreasing subsequence of π.
This observation easily generalizes as follows.

Given a sequence ,
the elements of each pile constructed by 
form a non-increasing subsequence of .


Hence, any increasing subsequence of  can contain at most one element in each pile.
This implies that () ≤ℓ.


Now we show that () ≥ℓ.
Using the piles, we can obtain an increasing subsequence of length ℓ,
in reversed order, as follows <cit.>:

  
  * Pick an arbitrary element of P_ℓ;
  
  * For 1 ≤ i < ℓ, let (h) be the element picked from P_i+1.
  Pick the element (h') that was the top element of P_i when (h) was pushed to P_i+1.


Since h' < h and (h') < (h) in each iteration,
the ℓ elements that are selected form an increasing subsequence of .
This completes the correctness proof for .

The proof above can be generalized to show the following characterization for the piles. 


(i) ∈ P_j if and only if 
a longest increasing subsequence of  ending at (i) has length j.





 §.§ Time and space complexity of 



Observe that at any point in time, the top elements of the piles are ordered increasingly from left to right.
Namely, 𝚝𝚘𝚙(P_k) < 𝚝𝚘𝚙(P_k') if k < k'.
This is observed in <cit.> for inputs with no repeated elements.
We can see that the statement holds also for inputs with repetitions.

  
  At any point in time during the execution of  and for any k and k' with 1 ≤ k < k' ≤ℓ,
  we have 𝚝𝚘𝚙(P_k) < 𝚝𝚘𝚙(P_k') if P_k and P_k' are nonempty.


We prove the statement by contradiction. Let i be the first index for which  pushes (i) to some pile P_j,
so that the  statement of the observation becomes false.

First assume that 𝚝𝚘𝚙(P_j) ≥𝚝𝚘𝚙(P_j') for some j' > j.
Let (i') be the element in P_j pushed to the pile right before (i).
By the definition of , it holds that 

    (i') ≥(i) = 𝚝𝚘𝚙(P_j) ≥𝚝𝚘𝚙(P_j').

This contradicts the minimality of i
because (i') was the top element of P_j before (i) was pushed to P_j.

Next assume that 𝚝𝚘𝚙(P_j') ≥𝚝𝚘𝚙(P_j) for some j' < j.
This case contradicts the definition of 
since (i) = 𝚝𝚘𝚙(P_j) ≤𝚝𝚘𝚙(P_j') and thus (i) actually has to be pushed to a pile
with an index smaller or equal to j'.

The observation above implies that
Line <ref> of Algorithm <ref> can be executed in O(log n) time by using binary search.
Hence,  runs in O(n log n) time.

The total number of elements in the piles is O(n) and thus  consumes O(n log n) bits.
If it maintains all elements in the piles,
it can compute an actual longest increasing subsequence in the same time and space complexity as described above.

Note that to compute (), it suffices to remember the top elements of the piles.
However, the algorithm still uses Ω(n log n) bits when () ∈Ω(n).



 §.§ A simple O(n)-bits algorithm


Here we observe that, when the input is a permutation π of {1,…,n},
(π) can be computed in O(n^2) time with O(n) bits of working space.
The algorithm maintains a used/unused flag for each number in {1,…,n}.
Hence, this noncomparison-based algorithm cannot be generalized for general inputs directly.

Let  be a sequence of integers without repetitions.
A subsequence i_1, …, i_ℓ is the left-to-right minima subsequence
if {i_1, …, i_ℓ} = {i |(i) = min{(j) | 1 ≤ j ≤ i }}.
In other words, the left-to-right minima subsequence is made by scanning  from left to right
and greedily picking elements to construct a maximal decreasing subsequence.

Burstein and Lankham <cit.>
showed that the first pile P_1 is the left-to-right minima subsequence of π
and that the ith pile P_i is the left-to-right minima subsequence of a sequence obtained from π
by removing all elements in the previous piles P_1, …, P_i-1.

Algorithm <ref> below uses this characterization of piles.
The correctness follows directly from the characterization.

It uses a constant number of pointers of O(log n) bits
and a Boolean table of length n for maintaining “used” and “unused” flags.
Thus it uses n + O(log n) bits working space in total.
The running time is O(n^2): each for-loop takes O(n) time and the loop is repeated at most n times.









§ AN ALGORITHM FOR COMPUTING THE LENGTH



In this section, we present our main algorithm
that computes () with O(s log n) bits in O(1/s· n^2log n) time for √(n)≤ s ≤ n.

Note that the algorithm here outputs the length () only.
The next section discusses efficient solutions to actually compute a longest sequence.

In the following, by P_i for some i we mean the ith pile obtained by (completely)
executing  unless otherwise stated.
(We sometimes refer to a pile at some specific point of the execution.)
Also, by P_i(j) for 1 ≤ j ≤ |P_i| we denote the jth element added to P_i.
That is, P_i(1) is the first element added to P_i and P_i(|P_i|) is the top element of P_i.

To avoid mixing up repeated elements,
we assume that each element (j) of the piles is stored with its index j.
In the following, we mean by “(j) is in P_i” that the jth element of  is pushed to P_i.
Also, by “(j) is P_i(r)” we mean that the jth element of  is the rth element of P_i.

We start with an overview of our algorithm.
It scans over the input O(n / s) times.
In each pass, it assumes that a pile P_i with at most s elements is given, which has been computed in the previous pass.
Using this pile P_i, it filters out the elements in the previous piles P_1, …, P_i-1.
It then basically simulates  but only in order to compute the next 2s piles.
As a result of the pass, it computes a new pile P_j with at most s elements such that j ≥ i + s.

The following observation, that follows directly from the definition of  and Observation <ref>, 
will be useful for the purpose of filtering out elements in irrelevant piles.


Let (y) ∈ P_j with j  i.
If (x) was the top element of P_i when (y) was pushed to P_j,
then j < i if (y) < (x), and j > i if (y) > (x).


Using Observation <ref>, we can obtain the following algorithmic lemma
that plays an important role in the main algorithm.


Having stored P_i explicitly in the additional memory and given an index j > i, 
the size |P_k| for all i+1 ≤ k ≤min{j, ()} can be computed
in O(n log n) time with O((|P_i| + j-i) log n) bits.
If () < j, then we can compute () in the same time and space complexity.


Recall that  scans the sequence  from left to right
and puts each element to the appropriate pile.
We process the input in the same way except that we filter out, and thereby ignore, the elements in
the piles P_h for which h <i or h >j.

To this end, we use the following two filters whose correctness follows from Observation <ref>.

(Filtering P_h with h<i.) To filter out the elements that lie in P_h for some h <i,
we maintain an index r that points to the element of P_i read most recently in the scan. Since P_i is given explicitly to the algorithm, we can maintain such a pointer r. 
 
When we read a new element (x), we have three cases.

  
  * If (x) is P_i(r+1), then we increment the index r. 
  
  * Else if (x) < P_i(r), then (x) is ignored since it is in P_h for some h <i.
  
  * Otherwise we have (x) > P_i(r). In this case (x) is in P_h for some h > i.


(Filtering P_h with h>j.)  The elements in P_h for h > j can be filtered without maintaining additional information as follows.
Let again (x) be the newly read element.

  
  * If no part of P_j has been constructed yet, then (x) is in P_h for some h ≤ j.
  
  * Otherwise, we compare (x) and the element (y) currently on the top of P_j.
  
    
  * If (x) > (y), then (x) is in P_h for some h > j, and thus ignored.
    
  * Otherwise (x) is in P_h for some h ≤ j.
  


We simulate  only for the elements that pass both filters above.
While doing so, we only maintain the top elements of the piles and additionally store the size of each pile. This requires at most O((j-i) log n) space, as required by the statement of the lemma.
For details see Algorithm <ref>.

The running time remains the same since we only need constant number of additional steps 
for each step in  to filter out irrelevant elements.
If P_j is still empty after this process, we can conclude that
() is the index of the newest pile constructed.



The proof of Lemma <ref> can be easily adapted to also compute the pile P_j explicitly. 
For this, we simply additionally store all elements of P_j as they are added to the pile.


Given P_i and an index j such that i < j ≤(), we can compute P_j
in O(n log n) time with O((|P_i| + |P_j| + j-i) log n) bits.


Assembling the lemmas of this section, we now present our first main result.
The corresponding pseudocode of the algorithm 
can be found in Algorithm <ref>.



There is an algorithm that, given an integer s satisfying √(n)≤ s ≤ n and a sequence  of length n, computes () 
in O(1/s· n^2log n) time with O(s log n) bits of space.


To apply Lemmas <ref> and <ref> at the beginning,
we start with a dummy pile P_0 with a single dummy entry P_0(1) = -∞.
In the following, assume that for some i ≥ 0 we computed the pile P_i of size at most s explicitly.
We repeat the following process until we find ().

In each iteration, we first compute the size |P_k| for i+1 ≤ k ≤ i+2s.
During this process, we may find () < i+2s.
In such a case we output () and terminate.
Otherwise, we find an index j such that i+s+1 ≤ j ≤ i+2s and |P_j| ≤ n/s.
Since s ≥√(n), it holds that |P_j| ≤ n/√(n) = √(n)≤ s.
We then compute P_j itself to replace i with j and repeat.

By Lemmas <ref> and <ref>,
each pass can be executed in O(n log n) time with O(s log n) bits.
There are at most () / s iterations, since in each iteration 
the index i increases by at least s or () is determined.
Since () ≤ n, the total running time is O(1/s· n^2log n).



In the case of the smallest memory consumption we conclude the following corollary.



Given a sequence  of length n,
() can be computed in O(n^1.5log n) time with O(√(n)log n) bits of space.








§ AN ALGORITHM FOR FINDING A LONGEST INCREASING SUBSEQUENCE



It is easy to modify the algorithm in the previous section
in such a way that it outputs an element of the final pile P_(),
which is the last element of a longest increasing subsequence by Proposition <ref>.
Thus we can repeat the modified algorithm n times
(considering only the elements smaller than and appearing before the last output)
and actually find a longest increasing subsequence.[
This algorithm outputs a longest increasing subsequence in the reversed order.
One can access the input in the reversed order and find a longest decreasing subsequence to avoid this issue.]
The running time of this naïve approach is O(1/s· n^3log n).


As we claimed before, we can do much better.
In fact, we need only an additional multiplicative factor of O(log n) instead of O(n) in the running time,
while keeping the space complexity as it is.
In the rest of this section, we prove the following theorem.




There is an algorithm that, given an integer s satisfying √(n)≤ s ≤ n and a sequence  of length n,  computes
a longest increasing subsequence of 
 in O(1/s· n^2log^2 n) time using O(s log n) bits of space.


Given a sequence  of length n,
a longest increasing subsequence of 
can be found in O(n^1.5log^2 n) time with O(√(n)log n) bits of space.


We should point out that the algorithm in this section is not a multi-pass algorithm.
However, we can easily transform it without any increase in the time and space complexity
so that it works as a sequential access algorithm.



 §.§ High-level idea

We first find an element that is in a longest increasing subsequence roughly in the middle.
As we will argue, this can be done in O(1/s· n^2log n) time with O(s log n) bits
by running the algorithm from the previous section twice, once in the ordinary then once in the reversed way. 
We then divide the input into the left and right parts at a near-mid element and recurse.

The space complexity remains the same and 
the time complexity increases only by an O(log n) multiplicative factor.
The depth of recursion is O(log n) and at each level of recursion the total running time is
O(1/s· n^2log n).
To remember the path to the current recursion, 
we need some additional space, but it is bounded by O(log^2 n) bits.




 §.§ A subroutine for short longest increasing sequences

We first solve the base case in which () ∈ O(n/s).
In this case, we use the original  and repeat it O(n/s) times.
We present the following general form first.

Let  be a sequences of length n and () = k.
Then a longest increasing subsequence of  
can be found in O(k · n log k) time
with O(k log n) bits.


Without changing the time and space complexity,
we can modify the original  so that

  
  * it maintains only the top elements of the piles;
  
  * it ignores the elements larger than or equal to a given upper bound; and
  
  * it outputs an element in the final pile.


We run the modified algorithm () times.
In the first run, we have no upper bound.
In the succeeding runs, we set the upper bound to be the output of the previous run.
In each run the input to the algorithm is the initial part of the sequence that ends right before the last output.
The entire output forms a longest increasing sequence of .[
Again this output is reversed. 
We can also compute the output in nonreversed order as discussed before.]

Since () = k, modified  maintains only k piles.
Thus each run takes O(n log k) time and uses O(k log n) bits.
The lemma follows since this is repeated k times and
 each round only stores O(log n) bits of information from the previous round.


The following special form of the lemma above holds
since n /s ≤ s when s ≥√(n).

Let  be a sequence of length n and () ∈ O(n/s) for some s with √(n)≤ s ≤ n.
A longest increasing subsequence of  
can be found in O(1/s· n^2log n) time with O(s log n) bits.




 §.§ A key lemma


As mentioned above, we use a reversed version of our algorithm.
 is the reversed version of :
it reads the input from right to left and uses the reversed inequalities.
 (See Algorithm <ref>.)
 computes the length of a longest decreasing subsequence in the reversed sequence,
which is a longest increasing subsequence in the original sequence.
Since the difference between the two algorithms is small,
we can easily modify our algorithm in Section <ref>
for the length so that it simulates  instead of .



Let Q_i be the ith pile constructed by  as in Algorithm <ref>.
Using Proposition <ref>,
we can show that for each (i) in Q_j,
the longest decreasing subsequence of the reversal of  ending at (i) has length j.
This is equivalent to the following observation.

  (i) ∈ Q_j if and only if
  a longest increasing subsequence of  starting at (i) has length j.


This observation immediately gives the key lemma below.

P_k∩ Q_() - k + 1∅ for all k with 1 ≤ k ≤().


Let (i_1), …, (i_ℓ) be a longest increasing subsequence of .
Proposition <ref> implies that (i_k) ∈ P_k.
The subsequence (i_k), …, (i_ℓ)
 is a longest increasing subsequence of  starting at (i_k)
since otherwise (i_1), …, (i_ℓ) is not longest.
Since the length of (i_k), …, (i_ℓ) is i_ℓ - k + 1 = () - k + 1,
we have (k) ∈ Q_() - k + 1.


Note that the elements of P_k and Q_() - k + 1 are not the same in general.
For example, by applying  to _1 = 2, 8, 4, 9, 5, 1, 7, 6, 3,
we get Q_1 = 3,6,7,9, Q_2 = 1,5,8, Q_3 = 4, and Q_4 = 2 as below. 
(Recall that P_1 = 2,1, P_2 = 8,4,3, P_3 = 9,5, and P_4 = 7,6.)
The following diagram depicts the situation. The elements shared by P_k and Q_() - k + 1 are colored and underlined.




  =0.5mm
  
    

    

    

    3 

    Q_1
  
  
    

    

    6 

    3 

    Q_1
  
  
    

    7 

    6 

    3 

    Q_1
  
  
    

    7 

    6 

    3     1 

    Q_1     Q_2
  
  
    

    7 

    6     5 

    3     1 

    Q_1     Q_2
  
  
    9 

    7 

    6     5 

    3     1 

    Q_1     Q_2
  
  
    9 

    7 

    6     5 

    3     1     4 

    Q_1     Q_2     Q_3
  
  
    9 

    7     8 

    6     5 

    3     1     4 

    Q_1     Q_2     Q_3
  
  
    9 

    7     8 

    6     5 

    3     1     4     2 

    Q_1     Q_2     Q_3     Q_4
  
  
    

          3             

    1     4     5     6 

    2     8     9     7 

    P_1     P_2     P_3     P_4
  





 §.§ The algorithm


We first explain the subroutine for finding a near-mid element in a longest increasing subsequence.

Let s be an integer satisfying √(n)≤ s ≤ n.
Given a sequence  of length n,
the kth element of a longest increasing subsequence of 
for some k with ()/2 ≤ k < ()/2 + n/s
can be found in O(1/s· n^2log n) time using O(s log n) bits of space.



We slightly modify Algorithm <ref> 
so that it finds an index k and outputs P_k such that |P_k| ≤ s and 
()/2 ≤ k ≤()/2 + n/s.
Such a k exists since the average of |P_i| for 
()/2 ≤ i < ()/2 + n/s is at most s.
The time and space complexity of this phase are as required by the lemma.

We now find an element in P_k∩ Q_() - k + 1.
Since the size |Q_() - k + 1| is not bounded by O(s) in general,
we cannot store Q_() - k + 1 itself.
Instead use the reversed version of the algorithm in Section <ref> to enumerate it.
Each time we find an element in Q_() - k + 1,
 we check whether it is included in P_k.
This can be done with no loss in the running time since P_k is sorted and
the elements of Q_() - k + 1 arrive in increasing order.


The next technical but easy lemma allows us to split the input into two parts at an element of a longest increasing subsequence
and to solve the smaller parts independently. 


Let (j) be the kth element of a longest increasing subsequence of a sequence .

Let _L be the subsequence of 1,…,j-1
formed by the elements smaller than (j).

Similarly let _R be the subsequence of j+1,…,||
formed by the elements larger than (j).

Then, a longest increasing subsequence of  can be obtained by concatenating
a longest increasing subsequence of _L, (j), and
a longest increasing subsequence of _R, in this order.


Observe that the concatenated sequence is an increasing subsequence of .
Thus it suffices to show that (_L) + (_R) + 1 ≥().

Let i_1, …, i_() be 
a longest increasing subsequence of  such that i_k = j.
From the definition, i_1, …, i_k-1 is a subsequence of _L,
and i_k+1, …, i_() is a subsequence of _R.
Hence (_L) ≥ k-1 and (_R) ≥()-k,
and thus (_L) + (_R) + 1 ≥().

As Lemma <ref> suggests, after finding a near-mid element (k), 
we recurse into _L and _R.

If the input ' to a recursive call has small ('), 
we directly compute a longest increasing subsequence.

See Algorithm <ref> for details of the whole algorithm.
Correctness follows from Lemma <ref>
and correctness of the subroutines.




 §.§ Time and space complexity


In Theorem <ref>, the claimed running time is O(1/s· n^2log^2 n).
To prove this, we first show that the depth of the recursion is O(log n).
We then show that the total running time in each recursion level is O(1/s· n^2log n).
The claimed running time is guaranteed by these bounds.



Given a sequence , the depth of the recursions invoked
by RecursiveLIS of Algorithm <ref> is at most log_6/5('),
where ' is the subsequence of  computed in Line <ref>.


We proceed by induction on (').
If (') ≤ 3 |'|/s, then no recursive call occurs,
and hence the lemma holds.
In the following, we assume that (') = ℓ > 3 |'|/s
and that the statement of the lemma is true for any sequence ” with (”) < ℓ.

Since ℓ > 3 |'|/s, we recurse into two branches on subsequences of '.
From the definition of k in Line <ref> of Algorithm <ref>,
the length of a longest increasing subsequence is less than ℓ/2 + |'|/s in each branch.

Since ℓ/2 + |'|/s < ℓ/2 + ℓ/3 = 5ℓ/6,
each branch invokes recursions of depth at most log_6/5 (5ℓ/6) = log_6/5ℓ - 1.

Therefore the maximum depth of the recursions invoked by their parent is at most log_6/5ℓ.



Given a sequence  of length n, 
the total running time at each depth of recursion excluding further recursive calls 
in Algorithm <ref> takes O(1/s n^2log n) time.


In one recursion level, we have many calls of RecursiveLIS
on pairwise non-overlapping subsequences of .
For each subsequence ', 
the algorithm spends time O(1/s |'|^2log |'|).
Thus the total running time at a depth is 
O(∑_'1/s |'|^2log |'|),
which is O(1/s n^2log n) since ∑_' |'|^2≤ ||^2 = n^2.


Finally we consider the space complexity of Algorithm  <ref>.

Algorithm <ref> uses O(s log n) bits of working space on sequences of length n.


We have already shown that each subroutine uses O(s log n) bits.
Moreover, this space of working memory can be discarded before another subroutine call occurs.
Only a constant number of O(log n)-bit words are passed to the new subroutine call.

We additionally need to remember the stack trace of the recursion.
The size of this additional information is bounded by O(log^2 n) bits
since each recursive call is specified by a constant number of O(log n)-bit words
and the depth of recursion is O(log n) by Lemma <ref>.
Since log^2 n ∈ O(s log n) for s ≥√(n), the lemma holds.









§ LOWER BOUND FOR ALGORITHMS WITH SEQUENTIAL ACCESS




An algorithm is a sequential access algorithm
if it can access elements in the input array only sequentially. In our situation this means that for a given sequence, accessing the ith element of the sequence directly after having accessed the jth element of the sequence costs time at least linear in |i-j|. As opposed to the RAM, any Turing machine in which the input is given on single read-only tape has this property. 

Note that any lower bound for sequential access algorithms in an asymptotic form is applicable to multi-pass algorithms as well
since every multi-pass algorithm can be simulated by a sequential access algorithm with the same asymptotic behavior.

Although some of our algorithms are not multi-pass algorithms,
it is straightforward to transform them to sequential access algorithms with the same time and space complexity.

To show a lower bound on the running time of sequential access algorithms with limited working space,
we need the concept of communication complexity (see <cit.> for more details).
Let f be a function.
Given α∈𝒜 to the first player Alice and β∈ℬ to the second player Bob,
the players want to compute f(α, β) together by sending bits to each other (possibly multiple times).
The communication complexity of f is the maximum number of bits transmitted between Alice and Bob
over all inputs by the best protocol for f.

Consider the following variant of the LIS problem: Alice gets the first half of a permutation
π of {1,…,2n} and Bob gets the second half. They compute (π) together.
It is known that this problem has high communication 
complexity <cit.>.


Let π be a permutation of {1,…,2n}.
Given the first half of π to Alice and the second half to Bob,
they need Ω(n) bits of communication to compute (π) in the worst case
(even with 2-sided error randomization).


Now we present our lower bound.
Note that the lower bound even holds for the special case where input is restricted to permutations.


Given a permutation π of {1,…,4n},
any sequential access (possibly randomized) algorithm computing (π) using b bits
takes Ω(n^2/b) time.


Given an arbitrary n>1, let π' be a permutation of {1,…,2n }.
We construct a permutation π of {1,…,4n} as follows. 
Let π'_1 = π(1),…,π(n) be the first half of π',
define π'_2 = 4n,4n-1,…, 2n+2 and
let π'_3 =π(n+1),π(n+2),…,π(2n) be the second half of π'.
Then we define π to be the concatenation of π'_1, π'_2, π'_3 and
the one element sequence π'_4 =2n+1, in that order.

It is not difficult to see that π is a permutation and that (π) = (π')+1.

To see the latter, observe that the concatenation of π'_2 and π'_4 is a decreasing subsequence of π.
Hence any increasing subsequence of π can contain at most one element not in π'.
On the other hand, any increasing subsequence of π' of length ℓ
can be extended with the element 2n+1 of π'_4 to an increasing subsequence of π of length ℓ + 1.

We say a sequential access algorithm traverses the middle if it accesses a position in π'_1 and then accesses a position in π'_3 or vice versa with possibly accessing elements in π'_2 but only such elements in meantime. Since each traversal of the middle takes Ω(n) time, it suffices to show that the number of traversals of the middle is Ω(n/b).

Suppose we are given a sequential access algorithm M that computes (π) with t traversals of the middle. 
Using M, we construct a two-player communication protocol for computing (π') with at most t b bits of communication. (A similar technique is described for streaming algorithms in <cit.>.)

Recall that the first player Alice gets the first half π'_1 of π'
and the second player Bob gets the second half π'_3 of π'.
They compute (π') together as follows.

  
  * Before starting computation, Alice computes π_A by concatenating π'_1 and π'_2 in that order,
  and Bob computes π_B by concatenating π'_2, π'_3, and π'_4 in that order.
  
  
  * They first compute (π) using M by repeating the following phases:
  
    
  * Alice starts the computation by M and continues while M stays in π1,…,3n-1 = π_A.
    When M tries to access π3n,…,4n, and thus a traversal of the middle occurs,
    Alice stops and sends all b bits stored by M to Bob.

    
  * Bob restores the b bits received from Alice to the working memory of M
    and continues computation while M stays in πn+1,…,4n = π_B.
    A traversal of the middle is occurred when M tries to access π1,…,n.
    Bob then stops and sends the b bits currently stored by M back to Alice.
  
  
  
  * When M outputs (π) and terminates, the currently active player outputs (π)-1 as (π')
  and terminates the protocol.

The two players correctly simulate M and, as a result, compute (π') together.
Since the algorithm M invokes t traversals, the total number of bits sent is at most t b.

Since tb ∈Ω(n) holds by Proposition <ref>, we have t ∈Ω(n/b) as required.


Recall that our algorithms for the LIS problem
use O(s log n) bits and runs in O(1/s n^2log n) time for computing the length
and in O(1/s n^2log^2 n) time for finding a subsequence, where √(n)≤ s ≤ n.
By Theorem <ref>, their time complexity is
optimal for algorithms with sequential access up to polylogarithmic factors of log^2 n and log^3 n, 
respectively.








§ CONCLUDING REMARKS

Our result raises the following question: “Do o(√(n))-space polynomial-time algorithms for LIS exist?”
An unconditional `no' answer would be surprising as
it implies SCP∩PolyL,
where SC (Steve's Class) is the class of problems that can be solved by an algorithm that simultaneously
runs in polynomial-time and polylogarithmic-space <cit.>.

A possibly easier question asks for the existence of a log-space algorithm.
For this question, one might be able to give some evidence for a `no' answer by showing
NL-hardness of (a decision version of) LIS.

We would like to mention some known results that have a mysterious coincidence in space complexity with our results.
For (1+ϵ)-approximation of (π) by one-pass streaming algorithms, it is known that
O(√(n / ϵ)·log n) bits are sufficient <cit.> 
and Ω(√(n/ ϵ)) bits are necessary <cit.>.

We were not able to find any connection here
and do not claim anything concrete about this coincidence.

To make the presentation simple, we used n to bound ()
in the time complexity analyses of the algorithms.
If we carefully analyze the complexity in terms of () instead of n when possible,
we can obtain the following output-sensitive bounds.

Let s be an integer satisfying √(n)≤ s ≤ n,
and let  be a sequence of length n with () = k.

Using O(s log n) bits of space,
() can be computed in O(1/s· k n log k) time 
and 
a longest increasing subsequence of 
can be found in O(1/s· k n log^2 k) time.









plainurl





