Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

If I have a loop within another loop, yet I know the inner loop will only run once, will this algorithm still be O(n^2)?

For i = 1 to n do

     For j = 1 to i do

          If (i==j) do

              For k = 1 to n

                  {Do stuff}

The very inner loop will run at most 1 time, since i will only equal j once per iteration of the second loop. Is this still n^3?

share|improve this question

2 Answers 2

up vote 7 down vote accepted

Think of it this way. Regardless of N, the innermost function will only ever execute once per execution of the second loop. This is to say, the amount of times it executes does depends on N linearly. This means that you can treat everything inside the first loop as a linear (O(n)) time operation (assuming {do stuff} is also constant time). If you consider the outermost loop, you see that you do something that takes O(n), n times. This means the overall runtime is O(n^2)

If you double N, there will be a total of N^2 extra iterations. Thus, the overall runtime is N^2.

share|improve this answer
    
Thank you very much! This is what I believed, yet the way i've always thought of nested loops confused me –  john May 16 '12 at 2:14
    
@john, not a problem. It's tricky to get right. It helps if you think about doubling N, and then asking how it effects the amount of times you do something. –  Oleksi May 16 '12 at 2:16
    
Huh? The first and THIRD loop depend on n. The conditional is only true once per execution of the second loop. We have two n^2 tasks here, the i-j loop pair and the i-k loop pair. The result is still n^2, though. –  Loren Pechtel May 16 '12 at 4:34
    
@LorenPechtel whoops. Sorry. I overlooked this. I updated the answer to reflect this. –  Oleksi May 16 '12 at 13:56

No, nested loops do not automatically mean your algorithm is O(n^k). The basic unit of work in your example is {Do stuff}, so you need to count how many times that will execute as n increases. You don't even need the j loop, since it only counts up from 1 to i and does nothing until it reaches i. Only on that one iteration does it actually do any work, so your example code is O(n^2).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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