time complexity of if else statement c#

user_9596503 0
Viewed 427

Which of the following two is more efficient from a processing / time complexity point - sorry just trying to get my head round time complexity and potential impact on computer processing time:

Option 1

if (condition1) {
  function1();
  function2();
} 
else {
  function3();
}

Option 2

if (condition1) {
  function1();
}
else {
  function3();
}

if (condition1) {
  function2();
}
else {
  function3();
}

Assuming function1() and function2() are both O(N), I think both option 1 and option 2 are O(N) time complexity. However if we could measure how quick both options run on the same computer, would option 1 be quicker or will there be minimal difference?

Thanks!

processing-efficiency time-complexity performance c#
2 Answers

The Time Complexity of an if is constant, i.e. O(1). So is the complexity of two if's.

If the functions are O(N), the complexity as a whole is O(N).

Time Complexity is not a measure of efficiency, but of scalability. It does not say how much resources (CPU cycles, memory, ...) an algorithm needs, but how much more it will grab when you double the input size.

Please wrap your head aorund that first; time complexity discusses different questions than the cost of individual operations. Don't mix that up.

As for the actual performance difference:

Option 2 will call function3() two times, so comparison depends on that.

If the functions do any siginificant processing, the difference between the two options will ne negligible, it will be dominated by the fluctuations of the functions.

Generally, performance of trivial operations (like an if) cannot be discussed without context.

For conditional jumps, the primary question is: how well predictable are they?
i.e. do they take the same branch most of the time? Two well-predictable conditional jumps are much better than one badly-predicted.

peterchen_313170

Option 2 cannot be faster than Option 1 since it is doing strictly at least as much work to figure out which functions to call. Note also that Option 2 results in two calls to function3 when condition1 is false, so in that case it's doing twice as much work (assuming the function is doing much more work than the snippets shown, which just figure out which functions to call).

In practice, these will probably have exactly the same performance (ignoring the repeated call to function3) because an optimizing compiler will recognize the opportunity to render binary code for option 2 that looks a lot more like what you'd expect for option 1. In the absence of optimizations, you're looking at one more conditional branch, which I think under reasonably assumptions could safely be characterized as being a minimal amount of extra overhead. Now, if this were in a tight loop, optimizations were turned off and condition1 were virtually always false, then maybe you'd see more of an issue (due to many missed branch predictions interrupting the pipeline) but I doubt it.

user_8472690
Related