# Big O time complexity

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

• 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)$. Feb 9, 2013 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? Feb 9, 2013 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) Feb 9, 2013 at 6:58

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)$.
• x++, x--, what does it matter.. anyways on any given computer it is $O(1)$ (-; Feb 9, 2013 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. Feb 9, 2013 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)$.. Feb 9, 2013 at 8:37