Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 0 down vote favorite

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

share|improve this question
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)$. – Ran G. Feb 9 at 3:57
@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? – NilRad Feb 9 at 4:02
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) – Ran G. Feb 9 at 6:58

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
x++, x--, what does it matter.. anyways on any given computer it is $O(1)$ (-; – Ran G. Feb 9 at 7:00
@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. – Bartek Feb 9 at 8:26
@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)$.. – Ran G. Feb 9 at 8:37
Thank you all of you :) – NilRad Feb 9 at 20:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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