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

Question

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?

kaya3 · Accepted Answer · 2019-12-19 10:21:14Z

3

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.

answered Dec 19, 2019 at 10:21

kaya3

51.6k7 gold badges87 silver badges118 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

christopherson Over a year ago

So if a nested loop has the same number of elements it would just be O(2n) which can be boiled down to linear time ?

kaya3 Over a year ago

@CodyVollrath I don't follow your question. Normally a nested loop would multiply the number of iterations because the inner loop would run once per iteration of the outer loop. The difference here is that the inner loop runs only once, regardless of the number of iterations of the outer loop.

christopherson Over a year ago

Sorry, I did not clarify, I meant that if the nested loop iterated over the same number of elements, and it only ran once, it would be O(2n). I already confirmed this myself but I asked at the time of reading this answer.

kaya3 Over a year ago

@CodyVollrath Yes, in that case it would be O(n) for the same reason.

Collectives™ on Stack Overflow

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

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related