algorithm - What is the runtime complexity of a switch statement?

Question

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

Answer 1

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.