8

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?

7

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.

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

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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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