Complexity where inner loop depends on outer loop

Question

For the following pseudocode, I would like to work out the number of operations as a function in input size n before putting it into Big-O-Notation:

for i ← 1 to n do
    for j ← 3 to 3i+n do
        // operation

So far, I think that the inner loop is equal to 3i + n - 2 operations for each iteration of the outer loop n. Yielding

n (3i + n - 2) = n^2 - 2n + 3ni

which simplifies to O(n^2).

But I'm not sure if I'm on the right track as I haven't seen any questions like this where the index of the outer loop is used in the inner loop.

Yes, O(n^2) looks like it is an upper bound for your loop. You can probably make the bound tighter with some math. — Tim Biegeleisen
– Tim Biegeleisen, Commented Mar 19, 2018 at 2:51
You can't. It is in Theta(n^2) (bound from both sides by n^2, it grows equally strong). — Zabuzard
– Zabuzard, Commented Mar 19, 2018 at 3:18
with some analytic algebra exec-time converges to 3n((n+1)/2-1)+n^2 which approaches 5/2n^2 — Abr001am
– Abr001am, Commented Mar 19, 2018 at 3:56

Zabuzard · Accepted Answer · 2018-03-19 03:58:34Z

4

Correct, it is in O(n^2). Even more than that, it is in Theta(n^2).

Explanation

The only thing that matters is how often // operation is getting executed. The computations for the loop itself, like the indices are all in Theta(1), so we can ignore them.

Therefore, count how often // operation is executed. That is n * (3i + n - 2), like you said.

However, the i changes. So you actually need to fully write it out:

Simplify this:

Which clearly is in Theta(n^2).

Formal definition proof

You can easily show that with the formal definition. Therefore, let us call the function f. We have

so it is in O(n^2). And we have

yielding Omega(n^2). Together this means f in Theta(n^2).

I chose the constants randomly. You could make it tighter, but you only need to find one for which it holds, so it doesn't matter.

Limit definition proof

Of course we could also easily show it using the limit definitions:

Which is > 0 and < inf, so f in Theta(n^2) (see Wikipedia:Big-O-notation).

The table for the results is

< inf is O(g)
> 0 is Omega(g)
= 0 is o(g)
= inf is omega(g).
> 0 and < inf is Theta(g)

For the limits we used L'Hôpital's rule (see Wikipedia) which informally says:

The limit of f/g is the same as the limit of f'/g', supposed the limit even exists.

Note

The analysis assumed that // operation is in Theta(1), otherwise you will need to account for its complexity too, obviously.

edited Mar 19, 2018 at 3:58

answered Mar 19, 2018 at 3:14

Zabuzard

26.3k8 gold badges61 silver badges92 bronze badges

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

2 Comments

Abr001am Over a year ago

it's precisely O(2n^2)

Zabuzard Over a year ago

@Abra001 Both are the exact same sets: O(2n^2) = O(n^2). And it's Theta additionally.

Collectives™ on Stack Overflow

Complexity where inner loop depends on outer loop

1 Answer 1

Explanation

Formal definition proof

Limit definition proof

Note

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Explanation

Formal definition proof

Limit definition proof

Note

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related