# 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
}
}

• 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
• You can find all you need at our reference question. See also algorithm-analysis+loops. Regarding babou's comment, see here. – Raphael Apr 12 '15 at 9:38

typically from my reading, for loops represent, in O(n), because the worst amount of time it takes for something in a for loop to be found is the last term, n. therefore a for loop within a forloop represents O(n^2)

• 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