Consider the algorithm MySolution below a What is the bigO O

Consider the algorithm MySolution below a) What is the big-O (O(n)) and big-Omega (ohm(n)) time complexity for algorithm MySolution in terms of w? Show all necessary steps. b) Trace (hand-run) MySolution for an array A = (60, 35, 81, 98, 14, 47). What is the resulting A? 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)? c) Can the space complexity of MySolution be improved? Explain how?

Solution

a) Most significant part of the given algorithm is line 4 and and 5
Line 4 contains a loop which runs n-2 times or we can say n times
For first iteration of loop from line 4, the loop in line 5 executes n-1 times
For second iteration of loop from line 4, the loop in line 5 executes n-2 times
For third iteration of loop from line 4, the loop in line 5 executes n-3 times
This fasion continues
So, total number of loop execution is
n-1 + n-2 + n-3 + .... + 1 = n(n+1)/2 = (n^2+n)/2 (approximately)
As per Big-Oh notation we can drop constant terms so after dropping 1/2 we have n^2+n
Now, again as per Big-Oh notation we only consider significant term having highest coeffecient.
So, we are left with n^2
Finally, we can say the Big-Oh complexity of given program is O(n^2)

b) Array A remain unchanged as there is no operation is done in array A