CODEWITHSUNDEEP
algorithmtime-complexity
manifold
manifold

Reputation: 437

runtime complexity of following algorithm

Given a sequence of as many as 10,000 integers (0 < integer < 100,000), what is the maximum decreasing subsequence? Note that the subsequence does not have to be consecutive. Recursive Descent Solution

The obvious approach to solving the problem is recursive descent. One need only find the recurrence and a terminal condition. Consider the following solution:

 1 #include <stdio.h>


 2  long n, sequence[10000];
 3  main () {
 4       FILE *in, *out;                     
 5       int i;                             
 6       in = fopen ("input.txt", "r");     
 7       out = fopen ("output.txt", "w");   
 8       fscanf(in, "%ld", &n);             
 9       for (i = 0; i < n; i++) fscanf(in, "%ld", &sequence[i]);
10       fprintf (out, "%d\n", check (0, 0, 999999));
11       exit (0);
12  }


13  check (start, nmatches, smallest) {
14      int better, i, best=nmatches;
15      for (i = start; i < n; i++) {
16          if (sequence[i] < smallest) {
17              better = check (i+1, nmatches+1, sequence[i]);
18              if (better > best) best = better;
19          }
20      }
21      return best;
22  }

Lines 1-9 and and 11-12 are arguably boilerplate. They set up some standard variables and grab the input. The magic is in line 10 and the recursive routine check. The check routine knows where it should start searching for smaller integers, the length of the longest sequence so far, and the smallest integer so far. At the cost of an extra call, it terminates automatically when start is no longer within proper range. The check routine is simplicity itself. It traverses along the list looking for a smaller integer than the smallest so far. If found, check calls itself recursively to find more

i think worst case would be when input is in completely reverse order like

10 9 8 7 6 5 4 3 2 1

so what is runtime complexity of this algorithm,i am having difficult time finding it...

Upvotes: 0

Views: 77

Answers (1)

MD Ruhul Amin
MD Ruhul Amin

Reputation: 4502

Your problem statement matches with Longest increasing sub-sequence problem.

You are not doing any memoization. In worst case your implementation complexity is O(n^n). Because on each recursive call it will generate (n-1) recursive call and so on. Try to draw a tree and check number of leaf. `

          n
        / \ \..........
       /   \            \
    (n-1)  (n-1) ...... (n-1)
   /  \
(n-2) (n-2)........(n-2)
`

Check out this linkLongest_increasing_subsequence.

Also for efficient implementation and more knowledge check this: Dynamic Programming | Set 3 (Longest Increasing Subsequence)

Upvotes: 2

Related Questions