What is the runtime complexity of a switch statement?

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:

• Java
• C/C++
• C#
• PHP
• Javascript

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.

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.