Switch statement in C++ - Time & Space Complexity

Time Complexity: Switch statement

O(1)

Understanding Time Complexity

We want to understand how the time it takes to run a switch statement changes as the number of cases grows.

Specifically, does adding more cases make the program slower, and by how much?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int exampleSwitch(int x) {
    switch (x) {
        case 1:
            return 10;
        case 2:
            return 20;
        case 3:
            return 30;
        default:
            return 0;
    }
}
    

This code returns a value based on the input using a switch statement with a few cases.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The switch statement performs a single jump or lookup based on the input value.
• How many times: Executes in constant time; no loops or repeated checks.

How Execution Grows With Input

Compilers typically optimize switch statements on integers to a jump table (dense cases) or binary search (sparse cases), keeping operations roughly constant.

Input Size (number of cases)	Approx. Operations
3	1 jump/lookup
10	1 jump/lookup
100	1 jump/lookup (or O(log n) worst case)

Pattern observation: Time remains constant (O(1)) or logarithmic at worst, independent of case count.

Final Time Complexity

Time Complexity: O(1)

This means the time to find the matching case is constant, regardless of the number of cases (thanks to compiler optimizations like jump tables).

Common Mistake

[X] Wrong: "Switch statements check cases one by one, so O(n) time."

[OK] Correct: C++ compilers optimize switches to jump tables (O(1)) for dense integers or binary search (O(log n)), not linear scans.

Interview Connect

Understanding switch optimizations shows knowledge of compiler behavior and real-world efficiency beyond naive analysis.

Self-Check

"What if the switch statement was replaced by a hash map lookup? How would the time complexity change?"

Practice

1. What is the main purpose of a switch statement in C++?

easy

A. To declare a variable

B. To repeat a block of code multiple times

C. To define a function

D. To choose which block of code to run based on a single value

Solution

1. Step 1: Understand the role of switch

   A switch statement checks one value and runs code matching that value.

2. Step 2: Compare with other options

   Repeating code is done by loops, functions define reusable code, and variables store data.

3. Final Answer:

   To choose which block of code to run based on a single value -> Option D

4. Quick Check:

   Switch selects code by value = A [OK]

Hint: Switch picks code based on one value quickly [OK]

Common Mistakes:

• Confusing switch with loops
• Thinking switch defines functions
• Mixing switch with variable declaration

2. Which of the following is the correct syntax to start a switch statement for variable choice?

easy

A. switch(choice) {

B. switch choice {

C. switch choice() {

D. switch(choice);

Solution

1. Step 1: Recall switch syntax

   The switch statement requires parentheses around the variable: switch(variable).

2. Step 2: Check each option

   switch(choice) { uses correct parentheses and opening brace. Others miss parentheses or use wrong punctuation.

3. Final Answer:

   switch(choice) { -> Option A

4. Quick Check:

   Correct switch syntax uses parentheses [OK]

Hint: Switch needs parentheses around variable [OK]

Common Mistakes:

• Omitting parentheses
• Using semicolon instead of brace
• Adding parentheses after variable name

3. What will be the output of this code?

int x = 2;
switch(x) {
  case 1:
    std::cout << "One";
    break;
  case 2:
    std::cout << "Two";
    break;
  default:
    std::cout << "Other";
}

medium

A. One

B. Two

C. Other

D. No output

Solution

1. Step 1: Check the value of x

   The variable x is 2.

2. Step 2: Match case in switch

   The switch matches case 2, so it prints "Two" and then breaks.

3. Final Answer:

   Two -> Option B

4. Quick Check:

   Value 2 matches case 2 = Two [OK]

Hint: Match variable value to case label [OK]

Common Mistakes:

• Forgetting break causes fall-through
• Choosing default when case matches
• Confusing output with case number

4. Identify the error in this switch statement:

int n = 3;
switch(n) {
  case 1:
    std::cout << "One";
  case 2:
    std::cout << "Two";
    break;
  default:
    std::cout << "Default";
}

medium

A. default case must be last

B. Variable n should be a string

C. Missing break after case 1 causes fall-through

D. case labels must be strings

Solution

1. Step 1: Check case 1 block

   There is no break; after case 1, so execution falls through to case 2.

2. Step 2: Understand consequences

   Without break, both "One" and "Two" print if n=1. This is usually unintended.

3. Final Answer:

   Missing break after case 1 causes fall-through -> Option C

4. Quick Check:

   Break prevents fall-through = A [OK]

Hint: Always add break after each case to stop fall-through [OK]

Common Mistakes:

• Forgetting break causes multiple outputs
• Thinking default must be last (it can be anywhere)
• Believing case labels must be strings

5. You want to write a switch statement that prints "Weekend" for cases 6 and 7, and "Weekday" for cases 1 to 5. Which code snippet correctly does this?

hard

A. switch(day) {
case 1: case 2: case 3: case 4: case 5:
std::cout << "Weekday";
break;
case 6: case 7:
std::cout << "Weekend";
break;
default:
std::cout << "Invalid";
}

B. switch(day) {
case 1:
case 2:
case 3:
case 4:
case 5:
std::cout << "Weekend";
break;
case 6:
case 7:
std::cout << "Weekday";
break;
default:
std::cout << "Invalid";
}

C. switch(day) {
case 1:
case 2:
case 3:
case 4:
case 5:
std::cout << "Weekday";
case 6:
case 7:
std::cout << "Weekend";
break;
default:
std::cout << "Invalid";
}

D. switch(day) {
case 1: case 2: case 3: case 4: case 5:
std::cout << "Weekend";
case 6: case 7:
std::cout << "Weekday";
break;
default:
std::cout << "Invalid";
}

Solution

1. Step 1: Group cases for weekdays and weekends

   Cases 1 to 5 print "Weekday"; cases 6 and 7 print "Weekend". Grouping cases with no code between them is correct.

2. Step 2: Check breaks and outputs

   switch(day) { case 1: case 2: case 3: case 4: case 5: std::cout << "Weekday"; break; case 6: case 7: std::cout << "Weekend"; break; default: std::cout << "Invalid"; } groups cases correctly and uses breaks to prevent fall-through. Others mix outputs or miss breaks.

3. Final Answer:

   Option A code correctly prints "Weekday" for 1-5 and "Weekend" for 6-7 -> Option A

4. Quick Check:

   Group cases + breaks = correct switch [OK]

Hint: Group cases without code, add break after each group [OK]

Common Mistakes:

• Missing breaks causing fall-through
• Swapping outputs for cases
• Not grouping cases properly