Question

Given the following Java code:
public static boolean f(int [] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] < arr[j]) // *HERE*
return false;}
return true;}
(i) Find the number of times the comparison marked by *HERE* will be evaluated for each input:
{1, 2}
{10, 20, 30}
{30, 20, 10}
{-4, 7, 1}
(ii) For an array of size ????, what is the big-oh runtime of this code in the worst case?

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)