Question

1. public int add100(int[] array) 
{
   if (array.length < 100)
  {
   return 0;
  }
   int sum = 0;
   for (int i = 0; i < 100; i++) {
   sum += array[i];
   }
   return sum;  
}    

2. int sum = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= i; j++) { sum++; sum++; } } for (int i = 0; i < n; i += 2) { sum++; }

3. nt sum = 0; for (int i = 1; i <= n; i++) { sum += i; } for (int j = 1; j <= 10; j++) { sum++; } for (int i = 0; i < n; i += 2) { sum++; }

A.	O(n2)
B.	O(n3)
C.	O(n)
D.	O(1)
E.	O(n log n)

Answer 1

Question 1:

public int add100(int[] array) 
{
   if (array.length < 100)
  {
   return 0;
  }
   int sum = 0;
   for (int i = 0; i < 100; i++) {
   sum += array[i];
   }
   return sum;  
}   

Analysis: Here, one for loop is there and inside the loop the loop is executing for i=0 to i<100. In other words, the loop is getting executed for finite number of times. Thus, the loop does not depend on variable 'n'. Thus, the time complexity of this code would be constant. Thus, O(1).

Question 2:

int sum = 0;

for (int i = 1; i <= n; i++)

{ for (int j = 0; j <= i; j++)

{ sum++; sum++; } }

for (int i = 0; i < n; i += 2)

{ sum++; }

Analysis: Here three for loops are there where two of them are consecutive. The first loop at line 2 execute for i=1 to i<=n and the consecutive loop execute for j=0 to j<=i. Thus basically the consecutive loop also execute till j<=n, since i will run upto i=n. Thus, two nested loops run for n times. The last for loop is independent.

So, the time complexity will be of order of n². Thus, O(n²).

Question 3:

int sum = 0;

for (int i = 1; i <= n; i++)

{ sum += i; }

for (int j = 1; j <= 10; j++)

{ sum++; }

for (int i = 0; i < n; i += 2)

{ sum++; }

Answer: Here, all the loops are independent. No nested loop is here. All the loops are independent and only the first loop executes for i=0 to i<=n i.e. for n times. Also all other loops are independent. Thus, the time complexity of this code segment would be of order of 'n'. Thus, O(n).

CONCLUSION:

Question 1: O(1).

Question 2: O(n²).

Question 3: O(n).