uestion 2 Consider the algorithm MvSolution below: Algorithm MySolution (A, n) I
ID: 3757465 • Letter: U
Question
uestion 2 Consider the algorithm MvSolution below: Algorithm MySolution (A, n) Input: Array A of integer containing n elements Output: Array B of integer containing n elements 1. fori-0 ton-1 do Res [i] =0 3. end for 4. fori-0 to n-2 do 5. forj-i+l ton-l do 6. ifAliKA] then Res [i] = Res [i] + 1 7. 8. else Res [i] = Res [i] + 1 10. end if 11. end for 12. end for 13. fori-0 to n-1 do 14. BResi]lAli) 15. end for 16. Return B What is the big-0 (00) and big-Omega () time complexity for algorithm Show all necessary steps a) Solution in terns of n? b) Trace (hand-nu) MvSolution for an array A = (88. 12. 94. 17. 2. 36.69). What is the resulting B? c) What does MySolution do? Explain that clearly and briefly given any arbitrary array A of n integers? d) Can the runtime of MySolution be improved easily? Explain how (i.e. re-write another solution(s) that does exactly what MySolution is doing more efficiently)? Can the space compl e) 100%Explanation / Answer
1. First for loops takes n steps = n
Second for loop takes n2 steps = n2
Third for loop takes n steps = n
Hence, time complexity = 2n + n2
Hence, Timecomplexity = BigO(n2)
2. The resulting B for A = [88,12,94,17,2,36,69] is B = [2,12,17,36,69,88,94]
3. MySolution method sorts the given array in ascending order. So, first for loop creates an empty array of length n. Then, we fiill that empty array, i.e, each element of RES array show the numbers of elements less in the 'A' array compare to the element present at ith position. Then, 3rd for loop fills the ith element of A array at Res[i] position in B array.
4. No runtime of MySolution can not be increased, but you can use many other sorting algorithims having time complexity of `O(nlogn)` or even `(n)` in best cases.
5. No runtime of MySolution can not be increased, but you can use many other sorting algorithims having space complexity of O(1) or O(n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.