0
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ Best case would be an array full of numbers greater than 0 $\endgroup$
    – user253751
    Apr 11, 2022 at 16:51
  • $\begingroup$ 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. $\endgroup$
    – Enterbot
    Apr 11, 2022 at 17:31
  • $\begingroup$ Doesn't matter, those will all take the same amount of time $\endgroup$
    – user253751
    Apr 11, 2022 at 17:45
  • 1
    $\begingroup$ Why do you think the upper bound is O(nlogn) and O(n^2) is wrong? $\endgroup$
    – user253751
    Apr 11, 2022 at 17:46
  • $\begingroup$ 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. $\endgroup$
    – Enterbot
    Apr 11, 2022 at 18:03

1 Answer 1

0
$\begingroup$

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).

The lower bound (best - case senario) is when the first 2 elements in the array are positive numbers so the algorithm will terminate instantly because of the return statement. Since in that senario the algorithm will make only a constant amount of comparisons - no matter the length n of the array - the time complexity will be O(1).

$\endgroup$
8
  • $\begingroup$ This is not what is meant by lower bound complexity. It's not about picking certain types of cases for which complexity is lower; it's about finding a function that is a lower bound on the complexity of all cases. $\endgroup$ Jul 20, 2023 at 13:26
  • 1
    $\begingroup$ There may be a misunderstanding. By lower bound you mean big omega notation (Ω(n)) or best case senario? Because if you mean the former then indeed O(n^2) Ω(n^2) and Θ(n^2). If you mean best case senario then O(1) is the correct time complexity. I am from Greece so i am not very familiar with the terminology. $\endgroup$
    – ChrisT
    Jul 21, 2023 at 13:51
  • $\begingroup$ Yes, and what qualifies as the best case scenario? Isn't it always O(1)? $\endgroup$ Jul 21, 2023 at 18:16
  • $\begingroup$ No, it is not always the case that best case senario in every algorithm will be O(1). Quicksort for example has O(n logn) as best case senario. Linear search from the other hand - as well as the algorithm that you've posted - has O(1) as best case senario. Best case senario means what is the fastest way for an algorithm to run. In quicksort there is no chance to be faster than O(n logn) for example, no matter how you arrange the elements. Ω(n^2) is a lower bound of a function in general. But i am not sure what of the 2 are you looking for. Did it help you? $\endgroup$
    – ChrisT
    Jul 21, 2023 at 21:59
  • $\begingroup$ Not really. Isn't the best case scenario for a sorting algorithm that the input is already sorted? Than you can decide that in O(1). If the best case scenario is a specific kind of input for which the problem can be solved quickly, then I think we can always find a best case scenario that can be processed in O(1) time. $\endgroup$ Jul 22, 2023 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.