1 Identify the worstcase time complexity for the algorithm b

1. Identify the worst-case time complexity for the algorithm below and prove your answer is correct. Please strongly justify your answer. You may make use of the identities below, which hold for any positive integer n:

i 2 e(1) Input: data: array of integers. Input n: length of data 1 Algorithm Loop Mystery 2 count Array(n) 3 for i 1 to n do count i i 5 end. 7 repeat 8 while is n and count 1 do count il -i 1 10 11 end 12 if i n then 13 Swap data [1] and data il 14 count il countlil 1 15 16 end 17 until i> n 18 return data

Solution

worst case complexity:-

line wise analyzing

1:O(1)

2:O(1)

3:O(n)// for loop...runs for i =1 to n

4:O(1)

5:O(1)

6:O(1)

7:O(1)

8:from 8 to17

complexity is : i*(i-1)! for i=1 to n

that is 1*1+2*1+3*2!+4*3!+.....+n*(n-1)!

using above equation :

it is O(n^2 n!)

The worst case complexity is O(n^2 n!)