Is this code's running time Big Theta (n^2)?

Question

public int calculateValue(int i, int j) {
    int count = 0;
    for(int r = 0; r < i; r++){
        for(int c = 0; c < j; c++){
            if(A[r][c] == 1){
                count++;
            }
        }
    }
    return count;
}

I have been trying to figure out if this code is running on Big Theta of n^2. I am certain it is O(n^2), but I am not sure if it is Big Omega of (n^2). Is there a simple way to determine this?

Note: the input array A is a simple 2D array of size n x n.

Answer 1

The cost should be expressed in terms of i and j, since those are the input variables.

• The outer loop runs for i iterations, the inner loop for j iterations.
• Their iteration counts are independent of each other.
• Assuming that A is simple 2-D array, the cost of the inner loop body is Θ(1).

Given these conditions, it is safe to multiply their costs together. Therefore the overall runtime is Θ(ij).