Big-O runtime of various search algorithms

Question

The hasTwoTrueValues method returns true if at least two values ​​in the boolean array are true . Provide Big-O runtime for all three proposed implementations.

// Version 1

 public boolean hasTwoTrueValues(boolean[] arr) { int count = 0; for(int i = 0; i < arr.length; i++) if(arr[i]) count++; return count >= 2; } 

// Version 2

 public boolean hasTwoTrueValues(boolean[] arr) { for(int i = 0; i < arr.length; i++) for(int j = i + 1; j < arr.length; j++ ) if(arr[i] && arr[j]) return true; } 

// Version 3

 public boolean hasTwoTrueValues(boolean[] arr) { for(int i = 0; i < arr.length; i++) if(arr[i]) for(int j = i + 1; j < arr.length; j++) if(arr[j]) return true; return false; } 

These are my answers:

• Version 1 - O(n)
• Version 2 - O(n^2)
• Version 3 - O(n^2)

I am really new to this Big-O notation, so I need guidance if my answers are correct / incorrect. If I'm wrong, could you explain and help me find out?

Answer 1

Version 1 is pretty simple and works linearly, so the runtime is O (n) on average.

Version 2 is a bit more interesting. It works with n (n-1) on average, which is O (n ² ). There is an early return in this loop, so it is quite possible that it might break even in the first two elements.

Version 3 is harder. You have to be careful. The second loop will only be executed if arr[i] is true . At the same time, the runtime should be placed in different categories.

• If all elements of the array are false, then your runtime will be O (n).
• If half the elements of the array are true, then you will run the second loop under the condition (n (n-1)) / 2, which is O (n ² ).
• If all elements of the array are correct, then you will work in O (n ² ). You will also exit immediately after the first two elements, but you are still using two loops to complete the action.

We can say with confidence that the average and worst execution time for version 3 will be O (n ² ). O (n) would be best, which is certainly possible.

Answer 2

In short, worst case time : Version 1: O(n)
Version 2: O(n^2)
Version 3: O(n)

---

More detailed analysis ...

For this algorithm, you will need to think about the best cases, the worst case, and the wait tool to get a meaningful comparison.

For each of them, the following should serve as an example:

 bestCase = [ true, true, ...] // the first two are true worstCase = [ false, false, ..., false] // all are false averageCase = [ true, ..., true, ..., false // second true value is found about half-way 

For all your algorithms, the best execution time is O(2) , which means constant time.

In the worst case, your first algorithm is O(n) , which means linear runtime. However, in the worst case scenario, your second algorithm will degenerate very specifically, since at each step you have one more element to check. You will get the sum n + (n-1) + (n-2) + ... , which will be evaluated to n(n-1)/2 , which, as you correctly said, is in O(n^2) and growing quadratically.

In the “worst case”, where everything is false (as we will see, this is actually not the worst option for version 3 ), your third algorithm actually works in linear time, since the if prevents the second loop from starting.

As it turned out, version 3 will never work in quadratic time: it will be linear in the average and worst case, since it scans linearly for the first true , and then scans the rest linearly for the second true only after detecting it, although it does not even work! Since you have two returns in your inner for-loop, once the first true value has been met, it will return true if the next nearest neighbor is true . However, if the next nearest neighbor is false , it immediately returns false and does not check any other values. This means that at the input:

 [ true, false, true ] 

version 3 will return false as soon as it sees a second false value. (Technically, I assume that you want this return false executed inside the for loop, in which case you also need to add { } , as well as with your first version. Although this is not always necessary, this helps clarify that this is happening , especially if this does not match your indentation at present. When missing, only the statement following it is included in the body of the / if loop.) I suspect that even if it is executed correctly, * version 3 will still have the worst result, random runtime that is linear, at the entrance:

 [true, false, false, ..., false] 

The first true one will cause it to scan n times in the inner loop, but then the outer loop will continue to work until n without restarting the inner loop, which will give you only 2n-1 operations, which of course are in O(n) .

If your { } correct, and it’s just your indentation, which is incorrect, then these analyzes may need a little change, but this is the kind of thinking that you need to apply to large O problems (and asymptotic analysis in general).