Question

(V). Given the following algorithm, answer relevant questions. Algorithm 1 An algorithm 1: procedure WHATISTHIS(21,22,...,n: a list of n integers) for i = 2 to n do c= j=i-1 while (j > 0) do if ra; then break end if 4j+1 = a; j= j-1 end while j+1 = 1 end for 14: return 0.02. 1, 15: end procedure Answer the following questions: (1) Run the algorithm with input (41, 02, 03, 04) = (3, 0, 1,6). Record the values of variables right after line 10 is executed. Placing all possible results in table below. ragas (2) What does the returned value (output) represent? (3) Using the number of comparison as the operation to count, what is the worst-case time complexity of the algorithm in Big-O notation.

Answer 1

Answer:

The folowing table represent each value after line 10 of the code is executed:-

1)

i	j	x	a1	a2	a3	a4
2	1	0	3	3	1	6
3	1	1	0	3	3	6
4	1	1	0	1	3	6
4	3	6	0	1	3	6

2) The return output represent that the procedure is used for sorting the given list. As it swaps every element by its previous element if the previous number is greater than the next number.

3)

The worst case complexity of this algorithm is when the given list of number are sorted in reverse order that is in dexcending order.

In this case we will need to swap in each iteration of j that is.

when i=2 , (j =1)

when i=3 , (j = 2,j=1)

when i=4, (j =3, j=2, j=1)

For all these values we need to swap.

that is for every outer loop we will have multiple internal loop.

if we look at the above case we will have number of swap as:-

1+2+3+4-----(n-1)

so according to sumation we have n(n-1)/2 swaps that is multiple of n2 swaps

So the Big-O notation will be O(n2)

Hope it clears your doubt, in case of any other doubt do write in comments.

Please up vote if it helps you :)