What would be the complexity for this relation?

The function:

for (int i=1; i<n²; i++)
for (int j=i; j<n; j++)
print(j)

Putting it into a relation, I got:

$$C1 + \sum_{i=1}^{n^2}(C2+\sum_{j=i}^n(C3))$$

After solving it

$$C1+C2n^2+C3n^3-(C3\frac{n^4}2 + C3\frac{n^2}2)+C3n^2$$

What I can't figure out is the complexity of this relation.

Solution (from the answer to this post):

$$C1 + \sum_{i=1}^{n^2}C2+\sum_{i=1}^n\sum_{j=i}^nC3$$

$$C1 + C2\sum_{i=1}^{n^2}1+\sum_{i=1}^nC3\sum_{j=i}^n1$$

$$C1 + C2(n^2-1+1)+\sum_{i=1}^nC3(n-i+1)$$

$$C1 + C2n^2+\sum_{i=1}^nC3n - \sum_{i=1}^nC3i + \sum_{i=1}^nC3$$

$$C1 + C2n^2+C3n\sum_{i=1}^n1 - C3\sum_{i=1}^ni + C3\sum_{i=1}^n1$$

$$C1 + C2n^2+C3n(n-1+1) - C3(\frac{n(n+1)}2) + C3(n-1+1)$$

$$C1 + C2n^2+C3n^2 - C3(\frac{n^2+n}2) + C3n = O(n^2)$$

Trace what happens with your code rather than simply plugging the limits into the summation formulas. The inner loop won't actually be performed $$n^2$$ times, since its limit will be reached as soon as $$i=n$$ in the outer loop.

In other words, your timing function should be $$C_1+\sum_{i=1}^{n^2}C_2+\sum_{i=1}^n\sum_{j=i}^nC_3=O(n^2)$$

• THANK YOU SO MUCH! Jun 16 '20 at 19:41

How did you get this factor: $$-(C_3 n⁴/2 + C_3 n²/2) + C_3n²$$ ?

Considering the formula you showed shouldn't it be something like this:

$$C_1 + \sum_{i=1}^{n^2}( C_2 + \sum_{j=1}^{n}(C_3)) = C_1 + n^2*(C_2 + n*C_3) = n^3*C_3 + n^2 * C_2 + C_1$$ ? (And with it being in $$O(n^3)$$)

Edit: I mistook that $$i$$ in $$j=i$$ for a $$1$$. In that case I don't see how that function fits in any $$O$$ class. The dominating factor ($$n^4$$) is negative and $$O$$ is supposed to be an approximation of the number of operations an algorithm performs related to its domain size. With that said, for a large enough $$n$$, your function becomes negative.

• Oh I see my mistake. I mistook that $i$ in $j=i$ for a $1$. In that case I don't see how that function fits in any $O$ class. The dominating factor ($n^4$) is negative and $O$ is supposed to be an approximation of the number of operations an algorithm performs related to its domain size. With that said, for a large enough $n$, your function becomes negative. Jun 16 '20 at 11:15