Complexity of recursion in nested loops in Dynamic and Non-dynamic programming

Question

I have written a basic example of dynamic programming in Java (shown below) which solves the Longest Increasing Subsequence problem (https://en.wikipedia.org/wiki/Longest_increasing_subsequence).

The function works but for a homework assignment, I am trying to find out the time complexity of this algorithm vs its non-dynamic equivalent.

I believe dynamic version is O(n^2) but for the non-dynamic equivalent I am very confused. I have tried and failed to write a non-dynamic version, but I think it would be comprised of a recursive call within nested (2) for loops. Would that imply exponential time complexity? Or even factorial time complexity?

I would be very grateful for any help in cracking this complexity conundrum or even producing a non-dynamic, recursive equivalent of the function I have written below.

Thanks in advance!


   public static int longest(int[] array) {

        int n = array.length;

        int[] results = new int[n];

        for(int i = 0; i < n; i++) {
            results[i] = -1;
        }

        int max = 1;
        for(int j = 1; j <= n; j++) {
            int current = memoized_longest(array, j, results);
            if(current > max) {
                max = current;
            }
        }

        return max;
    }


    public static int memoized_longest(int[] array, int n, int[] results) {

        if(results[n-1] >= 0) {
            return results[n-1];
        }

        if(n == 1) {
            results[n-1] = 1;
            return results[n-1];
        }

        int q = 1;

        for(int i = n - 1; i >= 0; i--) {
            if(array[i] < array[n - 1]) {
                 q = Math.max(q, 1 + memoized_longest(array, i+1, results));
            }
        }

        results[n-1] = q;
        return q;
    }

Lorenz · Accepted Answer · 2020-03-02 23:53:32Z

You almost had it:

public static int longest(int[] array) {
  int q = 0;
  for (int i = 0; i < array.length; i++) {
    q = Math.max(q, longest_at(array, i));
  }
  return q;
}

public static int longest_at(int[] array, int i) {
  int q = 1;
  for (int j = 0; j < i; j++) {
    if (array[j] < array[i]) {
      q = Math.max(q, 1 + longest_at(array, j));
    }
  }
  return q;
}

longest_at returns the length of the longest increasing subsequence ending at position i. Turning a recursive DP algorithm into a normal recursive algorithm is achieved by just dropping the memorization.

As for the runtime, we have the following recurrence relation:

T(n) <= T(1) + T(2) + ... + T(n-1)

T(n) is the runtime of longest_at(n). To compute longest_at(n), we must (potentially, if all elements before position n are smaller than array[n]) compute longest_at(1), longest_at(2), up to longest_at(n-1). This is reflected in the recurrence relation.

If T(1) = 1, then T(n) = 2^n - 1 is a solution.

Collectives™ on Stack Overflow

Complexity of recursion in nested loops in Dynamic and Non-dynamic programming

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related