-1
$\begingroup$

I have a question if I have my $k=300$ and my loop is like this :

for( int x = 0 ; x<n ; x--){
    for(int y=0 ; y<k; y++){
        ...
    }
}

Is this still $O(n^2)$? If no, why? Thank you :)

$\endgroup$
3
  • $\begingroup$ something is wrong there. Is $k=x$? if so then indeed it is $O(n^2)$, and exactly $n\frac{n+1}2$ (up to $\pm1$ in each term, due to less-than vs less-than-equal, etc.). If $k=300$, then this is exactly $300\cdot n=O(n) = O(n^2)$. $\endgroup$
    – Ran G.
    Feb 9, 2013 at 3:57
  • $\begingroup$ @RanG. Thank you, but I'm not following when you say O(n) = o(n^2) because O(n) is the best case scenario for my loop and o(n^2) is the worse... So, which one is then? $\endgroup$
    – NilRad
    Feb 9, 2013 at 4:02
  • $\begingroup$ Check this question to understand why $n=O(n)=O(n^2)=(O(f(n))$ for any $f$ that grows at least as fast as $n$ (i.e., it's an upper bound. Maybe not a tight bound, but still an upper bound) $\endgroup$
    – Ran G.
    Feb 9, 2013 at 6:58

1 Answer 1

4
$\begingroup$

Assuming that you meant x++ rather than x--, the complexity is $\Theta(nk)$. Since $k = 300$, you can simplify that to $\Theta(n)$. As Ran G. mentions, since $n = O(n^2)$, then your loop is also $O(n^2)$. It's also $O(2^n)$. But the tight analysis is $\Theta(n)$.

$\endgroup$
3
  • $\begingroup$ x++, x--, what does it matter.. anyways on any given computer it is $O(1)$ (-; $\endgroup$
    – Ran G.
    Feb 9, 2013 at 7:00
  • $\begingroup$ @RanG. if there will be x-- then x will be smaller then $n$ for a long time, until reach INT_MIN and turn to INT_MAX. $\endgroup$ Feb 9, 2013 at 8:26
  • $\begingroup$ @Bartek Indeed, however I meant that INT_MAX,INT_MIN are both O(1) (say, $2^{64}$ ?), so the loop anyhow runs less than, say $O(($INT_MAX$-$INT_MIN$)^2)=O(1)$.. $\endgroup$
    – Ran G.
    Feb 9, 2013 at 8:37

Your Answer

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

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