CODEWITHSUNDEEP
crecursiontime-complexitybig-o
Moon
Moon

Reputation: 23

Big-O of recursion

I have seen many questions of Big-O, but I couldn't quite figure out this one.

I was practicing some interview questions and I bumped into one where I have to find if a Pythagorean Triplet exists in an integer array. I figured out there is a easy O(n^3) way to to solve it, but I wanted to find a faster way.

My question is, is the code below O(n^2) or O(n^3)? I am confused because even though I only have 2 loops, I need to go through n times of n^2 in my worst case, which would be O(n^3).

public boolean findTriple(int[] array) {
return findT(0, array);
}

public boolean findT(int start, array) {
if(start == array.length-1) {
    return false;
}
int first = array[start];
for(int i = 0; i < array.length; i++) {
    for(int j = i+1; j < array.length; j++) {
        if(first*first == array[i]*array[i] + array[j]*array[j] ||
           array[i]*array[i] == array[j]*array[j] + first*first ||
           array[j]*array[j] == first*first + array[i]*array[i]) {
            return true;
        }
    }
}
return findT(start+1, array);
}

Upvotes: 2

Views: 108

Answers (1)

Tony Tannous
Tony Tannous

Reputation: 14876

Each time the function is called you do O(n^2) operations. You call your function n times. So total complexity is: O(n^3)

Upvotes: 2

Related Questions