Consider the algorithm MySolution below Algorithm MySolution

Consider the algorithm MySolution below Algorithm MySolution (A, n) Input: Array A of integer containing n elements Output: Array S of integer containing n elements for I = 0 to n - I do Var[i] = 0 end for for I = 0 to n - 2 do for j = i + l to n - l do if A [i], A[j] then Var[j] = Var[j] + 1 else Var[j] = Var[i] + I end if end for end for for i = 0 to n - l do S[Var[i]] = A[i] end for Return S What is the big-O (O (n)) and big-Omega (Q(n)) time complexity for algorithm MySolution in terms of n?? Show all necessary steps. Trace (hand-run) MySolution for an array A = (60, 35, 8, 98, 14, 47). What is the resulting A? What does MySolution do? Explain that clearly and briefly given any arbitrary array A of n integers? 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 complexity of MySolution be improved? Explain how?

Solution

1) Here First loop iterates for 0 to n-1 i.e n iterations hence O(n) and iteration inside it will take O(1) as this is just assigning a value.
Next for loop iterates for 0 to n-2 i.e n-1 iterations hence O(n-1) and the inner loop to it goes for i+1 to n-1 so O(n-1) and O(1) time for iterations inside it hence total for loop that starts at line 4 would be O(n-1)O(n-1)O(1)
And last for loop iterated for 0 to n-1 i.e n iterations O(n).
So total would be O(n)O(1)+O(n-1)O(n-1)O(1)+O(n).

Please provide what\'s written at line 6, its not clear and without that other parts cannot be answered.