common data Linked quetion :- 1) which of the following is correct recurrence formula of I(j) 2)how to evaluate this R.R

Question

At the end of it's 5^th Successful season,The siruseri Permier league is planning to give an award to most improved bowler over 5 years . For this an important Index will be computed for each bowler,This is defined as the longest Subsequence of strictly decreasing economy rate's by the bowler among all his matches over 5 season's.For example seasons are (10.0,5.0,8.9,6.7,4.2,5.5,2.2,3.4,6.0,2.3,2.0) so his improvement index is 7 based on sequence (10.0 ,8.9, 6.7, 5.5, 3.4, 2.3, 2.0)  

Now let E[1...........N] Donates a sequence of n economy rates for which improvement index is to be calculated 
for 1 $\leq$ j $\leq$ n,Let I[j] denotes the improved index for the prefix of score E[1.......j ] ending at E[j] 

 

1. Which of the following is correct recursive formulation of I(j) ?
   a) I(1)=1
   for j $\in$ 2,3,......,n I(j) = 1+ max {I(k)/ 1$\leq$K<j, E[k] > E[j]}
   
   b) I(1)=1
   for j $\in$2,3,......,n I(j) = 1+E(j-1) if E(j-1)<E(j)
   1 otherwise 
   
   C) I(1)=1
   for j $\in$2,3,......,n I(j) = 1+ max {I(k)/ 1$\leq$K<j, E[k] < E[j]}
   
   d)I(1)=1
   for j $\in$2,3,......,n I(j) = 1+E(j-1) if E(j-1) > E(j)
   1 otherwise 
2. How to evaluate this Recursive definition Using Dynamic programming?
   a) A 2-D table T of Size N X N to be filled row wise from T[1][1] to T[n][n]
   
   b) A 1-D table T of Size N  to be filled from T[n] to T[1] 
   
   C) A 2-D table T of Size N X N to be filled row wise from T[n][n] to T[1][1]
   
   d) A 1-D table T of Size N  to be filled from T[n] to T[1] 
3. What is the Time complexity in Dynamic programming ? 
   a) O(n)
   b) O(nLog n)
   c) O(n²)
   d) O(n³)

Answer 1

1. Answer is a. Reading the problem statement 4-5 times gives this :)

The current considered element must be smaller than ALL previous entries. So, b, c, and d are false. 

2. 1-D table filled from T[1] to T[n]

3. O(n)

Comments

Table construction is in O(n). That is correct. But why we need any function call after this? Because I[n] is our solution. If we don't use the table, then we need recursive calls and complexity will be O(n²) and storing the values in table (dynamic programming) makes the complexity O(n).

---

Sir,
i have a doubt. As we are constructing the table . And there are totally n distinct function call I(1) To l(n) That we need to store in the table. So for the table construction we need to evaluate these n distinct function. If we  see execution of  individual function then even if it would use previously calculated table value(using Dynamic programming) It would take O(n) Time to execute each Distinct function call. For ex: If we want to calculate I(j) Then it will take all previous value of table for k=1 To j-1 such that E(k) greater than E(j)           
now we will take max of these. So for each function  we will take O(n) Time and there are N distinct function call for the construction of the table
then by this tym should be O(n2)? I hav dis doubt .tell me plz

---

n distinct function calls or n distinct table look ups?

n distinct function calls take O(n²) and is not dynamic programming. 

n distinct table loop ups is dynamic programming and for each i, we need just one table look up (if we save the max also) and thus the overall time complexity is O(n).