Largest Increasing SubSequence with O(n^2) using Recursions

Question

LIS :The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest

Eg:

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

A longest increasing subsequence is 0, 2, 6, 9, 13, 15.

I can develop LIS using different ways like Dynamic programming and memorization techniques but, with a particular case where I like to implement LIS using recursion with time complexity of O(N^2).

As of I think using recursion we cannot implement algorithms with time complexity O(N^2).(Please correct me)

However i got this algorithm from google

Algorithm  LIS(A,n,x)
1: if n = 0 then
2:   return 0
3: m   LIS(A; n -1; x)
4: if A[n] < x then
5:   m =max(m; 1 + LIS(A; n-1;A[n]))
6: print(m)

Is this algorithm O(N^2)?

Can you please explain?

Why do you need O(N^2)? O(N) recursive adaptation can be implemented. Just make method return position and length of found sequence. — Basilevs

dev-masih dev-masih · Accepted Answer · 2014-11-06T02:49:40

This Algorithm Prints Maximum in a array First Argument (A) is the array, Second Argument (n) is the index of item that now checks for max and third Argument (x) is maximum in that time. in worst case you have a sorted array and in every check (if A[n] < x then) you have to update third Argument with max that means at most you have to check all of array.

the algorithm take a max from index n to n-1 and check that with max from n to n-2 and check that with max in n to n-3 index and it continues to check with n to 1 to get max item.

that means it is O(n+(n-1)+(n-2)+...+2+1) = O(n^2)

Sorry about Pic Quality :)

Largest Increasing SubSequence with O(n^2) using Recursions

1 Answers