1

In worst case(failed to find sum ending up return false), what would be the complexity equation of the code and what's BigO of it? I put // and number of times either 1, n, n^2 that I think right. Could you check if I am calculating it right?

public static boolean hasSum(int arr[], int sum){

        int n = arr.length;           //1

        for(int i =0; i<n; i++) {           // 1, n, n
            for(int j =0; j<n; j++) {      //1, n^2, n^2
                if(arr[i] +arr[j]==sum) {       //n^2
                    return true;
                }
            }
        }


    return false;      //1   (because it fails to find the sum)
}

So what I have is 3n^2 + 2n +4 , which is O(n^2)

I think I may be right on BigO, but not sure about the equation that I made.

Is it correct?

Thank you!

James Kang
  • 61
  • 5

0 Answers0