I am currently reading the paper On computing the length of longest increasing subsequences by Michael L. Fredman.

I'm struggling to understand parts of the proof of Theorem 3.5,
especially this bit:

Now consider the following enhancement $A^*$ of $A$. Whenever $A$ concludes that $L < k$, $A^*$ continues to completely sort $S$ [...]

This is used to show a bound for $L \ge k$, but why are they sorting the sequence?


1 Answer 1


Here is a sketch of the proof of Theorem 3.5:

  • If there is a comparison-based algorithm for LIS using $m$ comparisons in the worst case, then we can convert it to an algorithm which answers the question "is $L \geq k$" (for some fixed $k$) using $m$ comparisons.
  • Given an algorithm which answers the question "is $L \geq k$" using $m$ comparisons, we can convert it into an algorithm using $m + n \log k + O(n)$ comparisons which sorts the input whenever $L < k$.
  • Any comparison-based algorithm which sorts the input whenever $L < k$ must perform at least $\log S(n,k)$ comparisons (since it has at $S(n,k)$ possible outputs).
  • Consequently, every comparison-based algorithm for LIS must use at least $\log S(n,k) - n \log k - O(n)$ comparisons.
  • The theorem follows by choosing $k = \lfloor 3\sqrt{n} \rfloor$ and using the asymptotics of $S(n,k)$.

We sort the input in order to use a lower bound on sorting.


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.