One approach to calculate (i, j*) is the algorithm specified by Algorithm 2. In
ID: 3714964 • Letter: O
Question
One approach to calculate (i, j*) is the algorithm specified by Algorithm 2. In it, calls are made to a function evaluate which is specified by Algorithm 1. Algorithm 1 evaluate(A,i,j) 1: total-0 2: for k- i,... ,j do 3: tototal +Ak 4: return total Algorithm 2 subsequenceWithMaxSum 1(A) 1: n evaluate(A,answer 0,answer 1]) then answer *- (i,j) 7: return answer (a) [1 mark] Using big-O notation, what is the time complexity of the function evaluate in terms of the length of A? Justify your answer from the pseudocode. (b) [1 mark] Using big-O notation, what is the time complexity of the function subsequenceWithMaxSum 1 in terms of the length of A? Justify your answer from the pseudocodeExplanation / Answer
a.)Let's take a look at the evaluate function:
Its parameters are i and j.
When we first enter the loop in WithMaxSum() function, value of i=0, value of j=value of i=0.
Thus the first loop in evaluate() will result in for(k=0,...,0)
Thus it doesn't run.
When next we come, we have i=0 j=1.
Thus loop runs 1 time.
Next we come as i=0, j=2.
Loop runs 2 times.
When we come as i=1, j=3.
Loop runs 2 times.
Thus when we come with i=any arbitrary a(a<n-1) and j = any arbitrary b(b<n-1)
The loop in evaluate runs b-a times.
Thus the loop in evaluate runs j-i times.
Now, in the WithMaxSum(), we have :
i=o,...,n-1 -(1)
j=i,...,n-1 -(2)
Subtracting 1 from 2.
j-i=i.
Thus j=2i.
Therefore loop in evaluate() runs i times always.
And we have i from 0 to n-1, that is, in terms of length of A, evaluate() runs n times.
Thus the time complexity for evaluate(), we have O(n).
b) The time complexity of function WithMaxSum() can simply be calculated as:
for i=0,....,n-1 // This loop runs n times.
for j=i,....,n-1 // This loop always runs one less time than the outer loop, thus it runs n-1 times
evaluate() // has complexity of O(n).
Thus time complexity of the function is: n*(n-1)*(n)
Which will evaluate to highest n^3.
Thus for WithMaxSum() we have O(n^3).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.