Big-O running time of various search algorithms [closed]

Question

The method hasTwoTrueValues return true if at least two values in an array of boolean are true. Provide the Big-O running time for all three implementations proposed.

// 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 is O(n)
• Version 2 is O(n^2)
• Version 3 is 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 please explain and help me to learn?

Answer 1

Version 1 is pretty straightforward and runs linear, so the runtime of that is O(n) on average.

Version 2 is a bit more interesting. It runs with n(n-1) on average, which is O(n²). There's an early return in this loop, so it's definitely possible that it could break as early as the first two elements.

Version 3 is trickier. You have to be careful on this. The second loop will only run if arr[i] is true. The runtime of it has to be put into distinct categories then.

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

It's safe to say then that the average and worst runtime for Version 3 will be O(n²). Its best would be O(n), which is definitely possible.