You are given the following algorithm written in pseudocode where the entries of the input array...

 

Transcribed Image Text:

You are given the following algorithm written in pseudocode where the entries of the input array A and the input k are positive integer numbers. Also, assume that array A has sufficiently large number of entries.. ABC (A, k) 1 val - k 2 for i to k do 3 for j - k downto 1 4 if (A[1]*k < 10) then 5 valval 1 6 else val val +1 7 return val COST BEST-CASE TIMES WORST-CASE i. Fill in the above figure by considering each line's constant execution cost and the number times they are executed. ii. Compute the above algorithm's best-case and worst-case running times (i.e. T(k) values) by considering the single line costs and times of line executions. iii. What are the best-case and worst-case order of time complexities of the algorithm ABC? You are given the following algorithm written in pseudocode where the entries of the input array A and the input k are positive integer numbers. Also, assume that array A has sufficiently large number of entries.. ABC (A, k) 1 val - k 2 for i to k do 3 for j - k downto 1 4 if (A[1]*k < 10) then 5 valval 1 6 else val val +1 7 return val COST BEST-CASE TIMES WORST-CASE i. Fill in the above figure by considering each line's constant execution cost and the number times they are executed. ii. Compute the above algorithm's best-case and worst-case running times (i.e. T(k) values) by considering the single line costs and times of line executions. iii. What are the best-case and worst-case order of time complexities of the algorithm ABC?