Can someone explain me why the following algorithm for LIS is not O(n)?

Question

The following code traverses the list once and finds the LIS. I don't see why the DP algorithm should take O(n2).

//C
int lis(int *a, int l){
  if(l == 0) return 1;
  else if(a[l] > a[l - 1])  return  1 + lis(a, l - 1);
  else  return lis(a, l - 1);
}

int main(){
  int a[] =  { 10, 22, 9, 33, 21, 50, 41, 60 };
  cout << lis(a, sizeof(a)/sizeof(a[0]) - 1);
}

% erlang
lis([_H]) -> 1;
lis([H1, H2 |T]) when H1 > H2 ->  1 + lis([H2|T]);
lis([_H|T]) -> lis(T).

main() ->  lis(lists:reverse([ 10, 22, 9, 33, 21, 50, 41, 60 ])).

Answer 1

Your current implementation of lis/1 function is O(n), I don't see any reasons to doubt. But there is some problem. You implementation doesn't actually calculate valid LIS. Try

lis(lists:reverse([1,2,3,4,1,2]))

for error example. Longest increasing sequense is [1,2,3,4], right? But your algorith returns 6 as result.

• First error in your algorithm in that you increase result each time, when you encountered element that greater than previous. But you should increase result only if current element is greater that greatest element of your current LIS. So (according example above) you should remember 4 and not increase result after you detected then 2 is greater than 1.

• But this not only thing you have to do. Consider sequence 1 2 3 6 4 5. For 5 first elements LIS has length of 4. But there is TWO possible options there - either 1 2 3 4 or 1 2 3 6. Which you should take as actual LIS?

• And so on, and so on...

Another example comes directly from wiki page.

Sequence [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] has LIS [0, 2, 6, 9, 13, 15] (e.g., 6 elements), but your algorythm says 9.

And, (correct me, if I'm wrong), LIS implementation must return subsequence itself, but not only its length.