At the end of it's 5th 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.2, 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]

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

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]

What is the Time complexity in Dynamic programming ?

a) O(n)

b) O(nLog n)

c) O(n2)

d) O(n3)