-1
$\begingroup$

This question already has an answer here:

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  
  }  
} 
$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Apr 12 '15 at 9:40

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