Menu
I'd like to know what the worst-case runtime complexity of a switch statement is, assuming you have n cases.
I always assumed it was O(n). I don't know if compilers do anything clever, though. If the answer is implementation-specific, I'd like to know for the following languages:
622
Speed: A switch statement might prove to be faster than ifs provided number of cases are good. If there are only few cases, it might not effect the speed in any case. Prefer switch if the number of cases are more than 5 otherwise, you may use if-else too.
If each statement is "simple" (only involves basic operations) then the time for each statement is constant and the total time is also constant: O(1). In the following examples, assume the statements are simple unless noted otherwise.
Most would consider the switch statement in this code to be more readable than the if-else statement. As it turns out, the switch statement is faster in most cases when compared to if-else , but significantly faster only when the number of conditions is large.
Disadvantages of switch statementsfloat constant cannot be used in the switch as well as in the case. You can not use the variable expression in case. You cannot use the same constant in two different cases. We cannot use the relational expression in case.
It is at worst O(n). Sometimes (and this is language and compiler dependent), it translates to a jump table lookup (for "nice" switches that don't have too large a case range). Then that is O(1).
If the compiler wants to be funky, I can think of ways that the complexity can be implemented to be anything in between (e.g. perform binary search on the cases, for logn). But in practice, you're going to get eiher linear time or constant time.
184
The big-O complexity of a switch statement is not really the important point. Big-O notation refers to the performance as n increases towards infinity. If you have a switch statement big enough that the asymptotic performance is an issue then it is too big and should be refactored.
Apart from the readability issue, in Java and C# I think you would soon hit some internal limits for the maximum size of a single method.
For relatively small switch statements that are called often it would probably be more informative to measure the actual performance of the switch statement against other approaches that you could use instead. This measurement could be made by repeatedly performing the operation in a loop.
For larger switch statements I'd suggest refactoring to use a dictionary or similar data structure that has approximately O(1) performance even has n gets very large and it won't run into problems with the limited method size.
45
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
