Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does this piece of code with two for-loops not have Big O runtime of O(N^2)?

I am learning Big O notation in my algorithms class. I just done an online quiz for this week where we get a bunch of code blocks which we have to select the big O complexity for.

I got everything correct except this code block:

void printPairs(int[] arrX, int[] arrY) {
    for(int i = 0; i < arrX.length; i++) {
        for(int j = 0; j < arrY.length; j++) {
            System.out.println(arrX[i] + "," + arrY[j]);
        }
    }
}

I put in O(N^2) but I got it wrong which I am not sure why, there are two for-loops? And unfortunately I can not see the other options available or correct answer till the end of the week.

like image 493
user941027 Avatar asked Jan 27 '23 22:01

user941027


1 Answers

The runtime would be O(N²) if there was only one input i.e. one array passed as a parameter and iterated over in each of the two for-loops.

Because there are two inputs (arrX and arrY) for the method and both are used in each of the two for-loops.

The Big O runtime is O(XY) where X = arrX.length and Y = arrY.length.

Edit: As stated by @Oighea This is still a quadratic-time algorithm. It is just in two variables.

like image 84
Sash Sinha Avatar answered Jan 31 '23 09:01

Sash Sinha