Best and the worst case time complexity for 4 nested 'for' loops?

Question

What is the worst and the best time complexity for nested for loop?

int compare(int n, int A[][]) {
    int i, j, k, m;
    for (i=1; i<=n; i++) {
        for (j=1; j<=n; j++) {
            for (k=1; k<=n; k++) {
                for (m=1; m<=n; m++) {
                    if (A[i][j] == A[k][m] && !(i==k && j==m))
                        return 1;
                }
            }
        }
    }
return 0;
}

I tried to solve it on my own but getting really confused on how the inner most loop will add to the complexity.

Aside: in C arrays are rarely indexed from `1`. It is usual to index arrays from `0` such as `for(i = 0; i < n; i++)` — Weather Vane, Sep 12 '18 at 20:36
Did you mean `!(i==k || j==m)`? That is more difficult to get your head around than `if (A[i][j] == A[k][m] && i != k && j != m)` — Weather Vane, Sep 12 '18 at 20:39
I meant `not` for both `i == k` and `j == m` leading to condition where both the conditions are satisfied. — rjgupta21, Sep 12 '18 at 21:21

Kaidul · Answer 1 · 2018-09-12T20:27:23.693

2

The best case time complexity is constant, O(1). Best case will happen when the first and second element of the grid A are equal.

    1 1 x x x
A = x x x x x
    x x x x x
    x x x x x

The worst case complexity is O(n^4). Worst case will happen when all the elements of the grid A are unique.

    1  2  3  4
A = 5  6  7  8
    9  10 11 12
    13 14 15 16

edited Sep 12 '18 at 20:27

answered Sep 12 '18 at 20:22

Kaidul

15,409
15
81
150

Thank you @Kaidul That's what I had in mind but thought it was correct. – rjgupta21 Sep 12 '18 at 21:22

score 2 · Accepted Answer · edited Sep 12 '18 at 20:39

2

Best case: O(1), when A[1][1] = A[1][2]

Worst case: O(n⁴), when there is no repeated element -> you end up iterating whole array for each element of it.

Note that you could implement it more efficiently with a map or a set (will call it structure):

Iterate the array
If the structure already has A[i][j], return 1
Add A[i][j] to the structure
return 0 after array iteration ends

This will give you a worse case of O(n² log n) or O(n²), depending on the structure you use

edited Sep 12 '18 at 20:39

Srini

1,619
1
19
34

answered Sep 12 '18 at 20:22

juvian

15,875
2
37
38

Thanks @Srini and juvian Do you think by changing the logic the efficiency could be improved instead of using a map or set? – rjgupta21 Sep 12 '18 at 21:24
@RajatGupta not sure what you mean. Using a map or a set already means changing the logic – juvian Sep 13 '18 at 01:02
I meant in terms of the looping. But now I got your point. :) – rjgupta21 Sep 14 '18 at 13:36
For best case in the solution you and @Srini gave, `i != k` should be satisfied along with `j != m`. Therefore, A[1][1] = A[1][2] is not correct. Does it make sense or I'm making it more confusing? – rjgupta21 Sep 14 '18 at 14:54
@RajatGupta !(i==k && j==m) is equivalent to (i != k || j !=m) – juvian Sep 15 '18 at 22:55
Okay, got it. I didn't took into consideration `&&` condition. Thanks again. – rjgupta21 Sep 16 '18 at 22:44

Best and the worst case time complexity for 4 nested 'for' loops?

2 Answers2