For loop incremented by variable, time complexity

Question

for (int i = 1; i < a; i++){
    for(int j = 1; j < b; j = j + a){
        Function() <-- O(1)
    }
}

In this case, the outer loop will be executed 'a'times(O(a)), and the inner loop will be executed 'b/a' times(O(b/a)).

Then the total time complexity will be O(a * b/a ) = O(b)?

I am not this interpretation is right or not..

Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Paul Hankin, Jan 18 '17 at 01:44
why will the inner loop be executed `b/a` times? You probably mixed a few things up: the loop itself repeats `b` times (`Function()`) and is itself (`for(int j = 1...){...}`) repeated `a` times. — , Jan 18 '17 at 01:56

score 2 · Accepted Answer · answered Jan 18 '17 at 01:37

2

Well O(a * b/a) = O(b) is obviously right because there is the identity right there: O(b*a/a) = O(b*1) = O(b).

However, it seems like the time complexity is O(a*b*1) (assuming looping causes no overheads in time). The computational effort increases linearly with each individual loop size. That is the reason for O(a*b).

answered Jan 18 '17 at 01:37

Armen Avetisyan

1,140
10
29

the inner loop has a typo please check it again – NoSleep Jan 18 '17 at 02:23

score 1 · Answer 2 · answered Jan 18 '17 at 09:43

I think it is a good question, my thought is

The original complexity should be O(a) * O(b/a)

But before you jump into conclusion, you have to judge the cases:

If b <= a, then O(b/a) = O(1), so O(a) * O(b/a) = O(a)

If b > a, then O(b/a) = O(b/a), so O(a) * O(b/a) = O(b)

So combined these cases, I would say it is O(max(a,b))

score 0 · Answer 3 · answered Jan 18 '17 at 02:01

0

Armen is correct, the answer is O(ab). We can get the answer by these steps:

O((a-1)(b-1)(1))

=O(ab-a-b+1), which -a-b+1 can be ignored.

=O(ab)

answered Jan 18 '17 at 02:01

Tim

123
1
2
11

score 0 · Answer 4 · answered Jan 18 '17 at 11:22

O(b) is incorrect since you pass through the outer loop a times hence the answer must be at least O(a) (and, for all you know, b might be much smaller than a). The answer should depend on both a and b rather than b alone.

Counting carefully, you pass through the inner loop ceil((b-1)/a) times, hence the complexity is

O(a*ceil((b-1)/a))

But,

ceil((b-1)/a) <= (b-1)/a + 1

Thus

a*ceil((b-1)/a) <= a*((b-1)/a + 1) = b - 1 + a = a + b - 1

The 1 is asymptotically negligible, Hence the complexity is O(a+b).

Since O(a+b) = O(max(a,b)) this agrees with the answer of @shole.

For loop incremented by variable, time complexity

4 Answers4