CODEWITHSUNDEEP
javaloopsbig-oconcept
ddeamaral
ddeamaral

Reputation: 1443

How to find big O of this function

So I have this function that iterates through an 8x8 multidimensional array in Java. I am trying to understand the big O of this function in findTheBoss(). It searches a static 8x8 grid for a given string. I really want to understand how to find the Big O of a basic function such as this. I think this is O(n^2) but I'm not sure. Please help me to understand how to find the equation for this function.

public static void FindTheBoss(String[][] bossGrid, String bossName){

    for(int i=0; i < bossGrid.length; i++)
    {               
        //Iterate through each row?

        for(int j=0; j < bossGrid[i].length; j++)
        {

            if(bossGrid[i][j].equals(bossName))
            {

                System.out.println("Found '" + bossName + "' at position "+ i + "," + j);
                break;
            }
        }

    }   

}

Upvotes: 0

Views: 1426

Answers (2)

ffarquet
ffarquet

Reputation: 1283

You are almost right. But be careful, big O notation can be tricky, even if it is not that complicated when you are methodic.

Let's summarize what your code does : you receive a 2D array of size NxN and a String of length S and try to find the string (one or several times) in your matrix. Even if you break the loop some times, just assume that it doesn't happen that much. You are then just iterating over elements of this matrix and comparing two strings for each element.

Basically, if you say that this algorithm is O(N^2), it might be fair enough. But be careful to know what N is. If your grid can have N rows and M columns, you would say that the algorithm is O(N*M), which is O(N^2) only in the square case (this is a very common mistake).

However, I wouldn't say that this algorithm is O(N^2), but rather O(S*N^2). Indeed, what does equals do ? Comparison character by character until a character differs. In the case N is small but the string is insanely long, you see that it is important to take that into account.

Note : you can read this interesting thread about the complexity of String.equals(). It can obviously be faster than O(S) if you compare precomputed length or hash codes, but these are internal optimization and the worst case is still O(S).

Upvotes: 2

jojo
jojo

Reputation: 21

The explanation for uni-dimensional array in this post is quite decent. https://justin.abrah.ms/computer-science/how-to-calculate-big-o.html

In this post he talks about two dimensional arrays: https://justin.abrah.ms/computer-science/big-o-notation-explained.html There is a coursera link in his explanation about big-O for two dimensional arrays.

Upvotes: 1

Related Questions