# What is the time complexity (big O) of this nested for-loop? [duplicate]

What is the time complexity (big O) of this nested for-loop?
I believe it's either O(n) or O(n^2)

for (int i = n-1; i >= 0; i--){
for (int j = 0; j < i; j++){
main step
}
}


## marked as duplicate by Raphael♦Apr 12 '15 at 9:38

• Why do you believe that ? By the way, "either ... or", which means exclusive or, is inappropriate since anything that is $O(n)$ is also $O(n^2)$. – babou Apr 12 '15 at 8:22
• This is a naive, i.e. completely unstructured and unrigorous, approach. It's very easy to write loops that take time other than $\Theta(n)$. Also, sticking to $O$ does not tell you much. – Raphael Apr 12 '15 at 9:40