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  
  • 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

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)

| cite | improve this answer | |
  • $\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.