What is the complexity of a code that contains 2 for loops inside an if thats inside a for loop

Question

I've written the following code, and i was puzzled about how to calculate the time complexity of this code.

I think its O(n) but my friend says otherwise. What do you think?

public class Matrix {

    public static int hole(int[][]mat)
    {
        int col=0;
        int count1 = 0;
        int count0=0;
        for(int k=0;k<mat[0].length;k++)
        {
            count0 = 0;
            count1 = 0;

            if (mat[k][k] == 0)
            {
                // search column for ones
                for (int j = 0; j < mat.length; j++)
                {
                    if (mat[j][k] == 0 && j == k)
                        continue;
                    else if (mat[j][k] == 1)
                    {
                        count1++;
                    }
                    else
                        break;
                }
                //search the row
                for(int row = 0;row<mat.length;row++)
                {
                    if(mat[k][row]==0)
                    {
                        count0++;
                    }
                    else
                        break;
                }
                if(count0==mat.length&&count1==mat.length-1)
                {
                    return k;
                }
                
                
            }
            
        }
        System.out.print(count0 +"\n" +count1);
        return -1;
    }

}

if there is nested looping, usually it won't be O(n), very likely N^2 — Kent, Dec 22 '16 at 14:24

Amit Bhati · Accepted Answer · 2016-12-22T14:24:33.997

1

The complexity is O(N*M). The complexity of outer for loop is N multiplied by M of inner for loop.

edited Dec 22 '16 at 14:24

answered Dec 22 '16 at 14:23

Amit Bhati

5,569
1
24
45

3

The inner and outer loop has different lengths. O(n * m) would be more precise. – marstran Dec 22 '16 at 14:24
but there is an if statement,wouldn't that make it n+n,meaning O(n)? – naor.z Dec 22 '16 at 14:25
Remember that your are looking at the worst case. The worst case here is that the if-test always evaluates to true. – marstran Dec 22 '16 at 14:26
While calculating time complexity, you always check for worst case scenario. What if your if condition did occur, you can't call your code to be O(n). – Amit Bhati Dec 22 '16 at 14:26
Big O notation always means average case. The if statement only sometimes occurs. – Bambino Dec 22 '16 at 14:26
@Amit Bhati: That is not correct. You always talk about the average case. If you talk about Quicksort, you normally suppose O(n*log(n)). But the worst case is O(n^2). – Bambino Dec 22 '16 at 14:28
1

@AmitBhati No, he is not right. You are! :) Big O is worst case performance. – marstran Dec 22 '16 at 14:34
@marstran: I looked it up. Big O notation and worst / average case are not the same. What is interesting for a programmer is normally the average case. Defining the average case is not that easy though. – Bambino Dec 22 '16 at 14:36
1

@Bambino Big O notation is defined to describe the worst case performance. I wonder where you found what you describe. If you are describing average case performance with big O notation, you are doing it wrong. – marstran Dec 22 '16 at 14:40
Big O is a measure of asymptotic complexity. When I talk about Quicksort for example, I can say it is O(n^2) in the worst case and O(n*log(n)) in average case. So I use it to measure complexity under certain conditions which are defined as best / average / worst case. See https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation and https://stackoverflow.com/questions/14243666/is-big-o-notation-a-tool-to-do-best-worst-average-case-analysis-of-an-algori. Please tell me where you found that Big O always refers to worst case. – Bambino Dec 22 '16 at 14:45
@Bambino Big O has a very precise definition. You can find the definition of big O in this answer: http://cs.stackexchange.com/a/61 . Note the formulation "f grows at most as fast as g". That means that g, in this case n^2, is the upper bound of f. The function f __cannot__ grow faster than g. Ergo, big O notation describes the worst case performance. – marstran Dec 22 '16 at 14:59
@marstran The link you pointed to supports both positions. I think it really depends on what you are talking about. One answer says Big O means upper bound. Then you are right and I am wrong. Another question, linked to in the question you linked to (see https://cs.stackexchange.com/questions/23068/how-do-o-and-%ce%a9-relate-to-worst-and-best-case), implies Big O refers to Landau symbols. And then "per se, the two have nothing to do with each other" is correct. But my first answer telling it means average was wrong indeed. I will be more careful with that in the future. – Bambino Dec 22 '16 at 15:10

What is the complexity of a code that contains 2 for loops inside an if thats inside a for loop

1 Answers1