Big O: Which is better?

I'm new to Big-O notation, so I need a little advice. Say I have a choice of two algorithms: one with several for loops in a row, or one with a thrice nested for loop. For example, one is structured similar to this:

    for(int i = 0; i < a.length; i++)
    {
       // do stuff
    }

    for(int i = 0; i < b.length; i++)
    {
       for(int j = 0; j < c.length; j++)
       {
          // do something with b and c
       }
    }

    for(int i = 0; i < d.length; i++)
    {
       // do stuff
    }

And the other is structured this way:

for(int i = 0; i < a.length; i++)
{
 开发者_开发百科  for(int j = 0; j < b.length; j++)
   {
      for(int k = 0; k < c.length; k++)
      {
         // do stuff
      }
   }
 }

These examples may not seem practical, but I guess I'm just trying to illustrate my real questions: what's the big O notation for each method and will an algorithm with 3 nested loops always be less efficient than an algorithm with many twice nested loops (but not 3)?

what's the big O notation for each method

The big O of a loop with n steps nested in a loop with m steps is O(n * m). The big O of a loop with n steps followed by one with m steps is O(n + m) = O(max(n,m)).

So your first method is O( max(a.length, b.length * c.length, d.length)) and the second method is O( a.length * b.length * c.length). Which one is better depends on whether d.length is greater or less than a.length * b.length * c.length.

and will an algorithm with 3 nested loops always be less efficient than an algorithm with many twice nested loops (but not 3)?

It depends on how many steps each loops has in relation to the other. If all loops have the same number of steps, the 3 nested loops will always be worse than the 2 nested ones.

Not necessarily. Using a, b, and c to represent your variables, your first example is O(a + b * c + d) and your second is O(a * b * c). Probably the latter is worse, but it very much depends on the variables here - d could be the most important variable in the first example, and that would make it pretty hard to compare to the second - unless we're assuming the second doesn't have a d factor (say, optimizations of some sort)

Also - three loops doesn't necessarily mean less efficient, although this is often the case. if statements in the outer loops could cause the inner loops not to run, which could mean O(n²), despite having three nested loops. Sometimes the construction of the algorithm can appear to be one thing, but upon better analysis, we find that although it appears to be O(n³), it actually obeys O(n²).

In big-O you have the rule:

O(a + b) = O(max(a, b))

Therefore, if you run several loops after each other, the complexity of the algorithm is determined by the most-complex loop.

Your second example has O(a*b*c). This will be more complex than your first example if d < a*b*c. If d is not related to the other input lengths, you cannot compare the complexities.

[with a, b, .. I refer to a.length, b.length, ... respectively]