CODEWITHSUNDEEP
algorithmtime-complexity
Pedro Batista
Pedro Batista

Reputation: 1108

Do these two pseudo-algorithms have different execution times?

// -- Algorithm A
    int a = 1, b = 2;
    for (int n = 0; n < 100; n++)
    {
        int c = a + b + n;
        int d = a - b - n;
    }

// -- Algorithm B
    int a = 1, b = 2;
    for (int n = 0; n < 100; n++)
    {
        int c = a + b + n;
    }

    for (int n = 0; n < 100; n++)
    {
        int d = a - b - n;
    }

Should I try to use existing loops to make necessary operations? Or in the end the result is the same?

Upvotes: 0

Views: 61

Answers (4)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186833

In your current implementation

  int a = 1, b = 2;

  for (int n = 0; n < 100; n++)
  {
      int c = a + b + n;
      int d = a - b - n;
  }

you're doing nothing: both c and d are local vairables, which exist within for loop scope only; if optimizer is smart enough to find out that there's no possibility of integer overflow (both 1 + 2 + 100 and 1 - 2 - 100 are within [int.MinValue..int.MaxValue]) it can well eliminate the entire loop(s) with warning to developer.

Real world example is

 for (int n = 0; n < N; n++)
 { 
   f(n);
   g(n);
 }

Versus 

 for (int n = 0; n < N; n++)
   f(n); 

 for (int n = 0; n < N; n++)
   g(n);

where both f(n) and g(n) don't have side effects and N is large enough. So far so good, in the 1st case the execution time is

 T = f(0) + g(0) + 
     f(1) + g(1) + 
     ...  
     f(N - 2) + g(N - 2) +
     f(N - 1) + g(N - 1)

In the 2nd case 

T = f(0) + f(1) + ... f(N - 2) + f(N - 1) +
    g(0) + g(1) + ... g(N - 2) + g(N - 1)

As you can see, the execution times are the same (not only O(...)). In real life, it can be miniscule difference between two implementations: loop initialization and implementation details, CPU register utilizations etc.

Upvotes: 1

javidcf
javidcf

Reputation: 59731

Complexity-wise, both algorithms are O(n). Even if you consider multiplicative constants, you could say that one is n * 2 and the other one n + n, which is exactly the same.

In reality, though, it depends. One could argue that, since the second one performs twice as many branches, the performance will probably be worse (see this famous question), but ultimately it depends on the compiler, the particular input, the OS, etc.

Upvotes: 1

user987339
user987339

Reputation: 10727

In O(n) notation they will be the same. According to this:

you will firs have a Sum:

O(n) + O(n) = O(2n)

And then Multiplication by constant:

O(2n) = O(n)

so in the end it will be O(n)

Upvotes: 1

Mitesh Pant
Mitesh Pant

Reputation: 542

Definitely the first algo will be faster, but since the complexity is only increasing linearly, the second one is not bad. As far as you don't go quadratic both are good,

But if you end up writing n such loops then you have n^2 complexity which is bad

Upvotes: 0

Related Questions