CODEWITHSUNDEEP
time-complexitynested-loops
Vinh Quang Tran
Vinh Quang Tran

Reputation: 93

Time complexity of nested loop when inner loop only run once?

I have the following code and am trying to figure out its time complexity:

int sum(int m, int n, int K) {
    int s = 0;
    for (int i = 0; i < n; i++) {
        s += i;
        if (i == K % 2) {
            for (int j = 0; j < m; j++) {
                s += j;
            }
        }
    }
    return s;
}

According to the code, the outer loop runs at O(n) and the inner loop runs at O(m). However, the inner loop is executed only once (when i is equal to K % 2). I'm not sure whether the time complexity when it only run once will be O(nm) or O(n + m). Currently, I doubt that the complexity should be O(n + m). Can someone explain this case for me?

Upvotes: 2

Views: 591

Answers (1)

kaya3
kaya3

Reputation: 51142

It's O(m + n), because the inner loop only runs once.

The reason you normally would multiply the O(m) complexity of the inner loop by n is because normally, the inner loop is executed n times. We should multiply the complexity of each operation by how many times it's done. In this case, the O(m) operation is executed once, so you should multiply by 1, not n.

More concretely, the assignment s += i; and the comparison i == K % 2 are done n times each in total, and the assignment s += j; is done m times in total, so the total number of steps is O(m + n). There is no operation which is performed mn times, or any multiple of mn times.

Upvotes: 3

Related Questions