-1
$\begingroup$

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)$

$\endgroup$
1
$\begingroup$

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)$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ THANK YOU SO MUCH! $\endgroup$ – Ghost Jun 16 at 19:41
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Pedro Costa Jun 16 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.