2

so I have this really complex nested loop that I need to find the complexity of. The code is given below:

1. int c = 0;
2. for (int i = 1; i <= n; i++)
3.   for (int j = 1; j <= n; j++)
4.     for (int k = 1; k <= i + j; k += 3)
5.       c++;
6. return c;

So I know that the complexity is in O(n^3), but I need to know how to mathematically prove. Below shows the frequency of execution of each line.

1. 1
2. n
3. n(n-1)
4. No idea how to do this
5. No idea
6. 1

Can someone please help me out with the 4th and 5th step? It is really confusing as k goes from 1 to (i+j).

Improve this question
0

4 Answers 4

Reset to default
1

We can prove the complexity mathematically. The total number of iterations can be represented like (unfortunately latex is not supported)

sum_j=1^n sum_i=1^n (i + j) / 3

If you draw up the grid of i and j values and their sum i + j, you can see this too.

This is equivalent to

sum_j=1^n {[n(n + 1)/2 + nj] / 3}

Which can be further simplified to

{n[n(n + 1)/2] + n[n(n + 1)/2] / 3}

Which after evaluation gives

(n^3 + n^2) / 3

And this is of the order O(n^3).

The number of iterations with step being 1 instead of 3 can be proven programmatically (code in Python)

c = 0
n = 4 # change n for testing, slow
for i in range(1, n + 1):
  for j in range(1, n + 1):
    for k in range(1, i + j + 1):
      c += 1
assert(c == (n ** 3 + n ** 2))
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

That said, dividing the iterations by 3 isn't exactly "correct" since it's more of a floor function, but my math can't handle that.
Well if this is true, then for n=5, the value of c is 100. But when I run the code, the value of c is 58. Could you please let me know what I'm missing out on?
@ppaloo Your code runs k in steps of 3. The "proof" program is for k in steps of 1, since the sum i + j can never always be a perfect multiple of 3. It's difficult to construct an exact mathematical proof with a floor function.
@ppaloo Anyway for n = 5 the value of c is 150 not 100.
On further thought, it might be a ceiling function instead. The reason for c not being exact is the same though. You can only estimate.
0

Line 4:

i is O(n).
j is O(n).
Therefore, i+j is O(n).
Having a constant step of 3, making (i+j)/3 steps, is O(n).
This inner loop will run for n*n*k iterations, where
    k is the summation of ceil[(i+j)3] over their ranges.
    k will be roughly (n+2)/3.

Line 5:

Increment is O(1).

That should finish your derivation.

Improve this answer

5 Comments

Shouldn't the kth loop run for n(n-1)(2n/3)? Because the jth loop runs for (n-1) times right?
(1) That difference does not affect the computational complexity; (2) No, i and j have the same iteration limits.
Well if this is true, then for n=5, the value of c is 83 (from n*n*(2n/3)). But when I run the code, the value of c is 58. Could you please let me know what I'm missing out on?
You're missing that I made a computational error. Adjusting my answer ...
Most of all, why are you concerning yourself with the exact value of c? Your question asks about the computational complexity, which is the limit of time increase as a function of n, c is a reasonable metric of time, but the specific value for small n is not something over which to lose study time.
0

The program does for each (i,j) ∈ [n] X [n] a O(i+j) operation.
We can say it's a O(i) operation and then O(j) operation and the complexity remains the same.
Thus, for each i we do O(n*i) [for each j (n times), we do O(i)] and O(1 + 2 + ... + n) = O(n^2). Obviously, O(n*i) + O(n^2) = O(n^2) and we do this n times for a total of O(n^3).

Improve this answer

Comments

0

Since the only thing we care about is the O complexity, this can be transformed as long as we are within constant factors:

1) k += 3 => k++ changes runtime with a constant factor between [1, 3];

2) for (int i = 1; i <= n; i++) => for (int i = n/2; i <= n; i++): constant factor between [0.5, 1];

3) for (int j = 1; j <= n; j++) => for (int j = n/2; j <= n; j++): constant factor between [0.5, 1];

4) now i + j is between n and 2n, so for (int k = 1; k <= i + j; k += 3) => for (int k = 1; k <= n; k += 3): constant factor between [0.5, 1].

After these, the program is transformed as:

1. int c = 0;
2. for (int i = n/2; i <= n; i++)
3.   for (int j = n/2; j <= n; j++)
4.     for (int k = 1; k <= n; k ++)
5.       c++;
6. return c;

And it's easy to see c == n ** 3 / 4, which means the transformed program has a complexity of O(n^3).

Note this also proves the program runs within Ɵ(n^3).

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.