Question

Given the following Java code:

Answer 1

Answer:

See explaination

Explanation:

{1, 2}

Runs only once for 1 < 2

{10, 20, 30}

Runs 1 for 10 < 20

Runs 1 for 10 < 30

Runs 1 for 20 < 30

Total 3 times

{30, 20, 10}

Runs 1 for 30 < 20

Runs 1 for 30 < 10

Runs 1 for 20 < 10

Total 3 times

{-4, 7, 1}

Runs 1 for -4 < 7

Runs 1 for -4 < 1

Runs 1 for -7 < 1

​​​​​​​Total 3 times

Generalizing it will run for n*(n-1)/2 so for 2 element it will run for 2*1/2 = 1

For 3 element it will run for 3*2/2 = 3 times

(ii) (3 points) For an array of size , what is the big-oh runtime of this code in the worst case?

Time complexity in Worst case is O(n^2). Reason being it uses two for loop where first loop runs for n time and the second loop runs for n*n time in worst case hence its O(n^2)