Search code examples
time-complexitybig-oasymptotic-complexitycode-complexity

Unsure if my complexity analysis is correct


Attempting to find a Big-O estimation of this code chunk:

int a[][] = new int[m][n];
int w = 0;
for (int i = 0; i<m; i++) {
    for(int j = 0; j<n; j++) {
        if ( a[i][j]%2 == 0) {
            w++;
        }
    }
}

I made an esimation and simplified: O(m)O(n)O(1) => O(mn)

It looks like all cases will be O(mn) because it doesn't matter if the O(1) operation executes or not, is this correct? Or are there best/worst/average cases?

Appreciate any insight!

Thank you


Solution

  • It is O(mn) here because of the 2 loops (one of which is nested in another). O(1) doesn't make sense here. The if doesn't count. There is no break in it so it won't affect the whole traversal for both loops. There are no best or worse here, again because the if does not change the flow nor incrementing w affects the loops in anyway.