# What is the time complexity of this Java program?

Below is the code.

public static boolean twoPositive(int[] num) {
int i = 0;

while ( i < num.length ) {
int j = i + 1
while (j < num.length) {
if (Math.min(num[i], num[j]) > 0)
return true;
j++;
}
i++;
}
return false;
}


From my own understanding, as there is a nested loop, this is of O(n^2), which is the upper bound. It also seems to me that the lower bound is of O(n^2), as regardless of the array, it still has to go through both loops. Is this reasoning correct?

Also, would this mean that every array has exactly the same performance? I know that if an array has two positive integers, it would return true and go through less operations that an array with no positive integers. However, both go through the inner loop, and as both have O(n^2), they have the same runtime.

What do you guys think?

• Best case would be an array full of numbers greater than 0 Apr 11, 2022 at 16:51
• Would the worst case be the following three things, an array with no positive numbers, an array with the first number positive, and the rest non-positive, and an array with the last number positive, but all the rest non-positive? Also, it seems to me that the lower bound would be omega(n) and the upper bound would be O(nlogn). O(n^2) is wrong. Apr 11, 2022 at 17:31
• Doesn't matter, those will all take the same amount of time Apr 11, 2022 at 17:45
• Why do you think the upper bound is O(nlogn) and O(n^2) is wrong? Apr 11, 2022 at 17:46
• Originally, I assumed that the upper bound was O(n^2). However, my professor marked this as wrong. Thus, I am figuring out other options and I genuinely confused. On second thought, I think that it is O(n), since the second while loop is conditional on the value being positive. Hence, it seems that that the two loops are distinct from each other. Apr 11, 2022 at 18:03

The upper bound (worst - case senario) is when there are 1 or 0 positive numbers in the array because the algorithm will terminate only when i is equal to the number of elements of the array. In this case the time complexity is O(n^2) because there is a nested loop. So for i = 0 ther will be n-1 comparisons for i = 1 n-2 comparisons ... so the total comparisons will be $$\sum_{i=1}^{n-1} i = \frac{(n-1)(n)}{2} = \frac{n^2}{2} - \frac{-n}{2}$$ which is O(n^2).