Consider the algorithm MySolution below a) What is the big-O (O(n)) and big-Omeg
ID: 3924248 • Letter: C
Question
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?Explanation / Answer
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