It is correct to say C's switch is O(1).
Theoritically speaking, BrowserUK is also wrong when he said O(1) means test once. However he had something in () said "in this case", which made himself "politically" right ;-)
Strictly speaking, O(1) means that the cost is a constant, not a function of any variable, thus it is considered ideal, as the cost is 100% predictable. The complexity (worst scenario cost) of the switch statement is determined at the coding time, not base on the input data at execution time.
C's switch statement falls into this category. I personally believe that there is a benefit to have it in Perl.