Big O: Which is better?

Question

I'm new to Big-O, so I need some advice. Let's say I have a choice of two algorithms: one with several for loops in a row or one with a thrice-nested loop. For example, one of them is similar to the following:

    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 seem impractical, but I assume that I'm just trying to illustrate my real questions: what is the big notation for each method and will an algorithm with 3 nested loops always be less efficient than an algorithm with many double nested loops (but not 3)?

Answer 1

what a big notation for each method

O n , m, O(n * m). O n , m, - O(n + m) = O(max(n,m)).

, - O( max(a.length, b.length * c.length, d.length)), - O( a.length * b.length * c.length). , , d.length a.length * b.length * c.length.

3 , ( 3)?

, . , , .

Answer 2

. a, b c , - O (a + b * c + d), - O (a * b * c). , , : d , - , t (, - )

- , . if , , O (n ²), . , , O (n ³), O (n ²).

Answer 3

In big-O, you have a rule:

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

Therefore, if you run several cycles one after another, the complexity of the algorithm is determined by the most complex cycle.

In your second example, there is O (a * b * c). This will be more complicated than your first example if d <a * b * s. If d is independent of other input lengths, you cannot compare complexity.

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