Use cases - Time & Space Complexity

Time Complexity: Use cases

O(n)

Understanding Time Complexity

When we look at use cases in programming, we want to know how the time a program takes changes as the input grows.

We ask: How does the program's work increase when we give it more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdio.h>

void printNumbers(int n) {
    for (int i = 0; i < n; i++) {
        printf("%d\n", i);
    }
}

int main() {
    printNumbers(5);
    return 0;
}
    

This code prints numbers from 0 up to n-1, showing a simple use case of a loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that prints each number.
• How many times: It runs exactly n times, once for each number from 0 to n-1.

How Execution Grows With Input

As n grows, the number of print operations grows the same way.

Input Size (n)	Approx. Operations
10	10 prints
100	100 prints
1000	1000 prints

Pattern observation: The work grows directly with the input size; double the input, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the size of the input.

Common Mistake

[X] Wrong: "The loop runs faster because it just prints numbers quickly."

[OK] Correct: The speed of printing doesn't change the fact that the loop runs once per input item, so time still grows with n.

Interview Connect

Understanding how simple loops grow with input size helps you explain your code clearly and shows you know how programs behave as data grows.

Self-Check

"What if we added a nested loop inside the existing loop? How would the time complexity change?"

Practice

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

easy

A. To declare variables

B. To choose between multiple actions based on the value of a variable

C. To define a function

D. To repeat a block of code multiple times

Solution

1. Step 1: Understand the role of switch

   The switch statement is used to select one of many code blocks to execute based on a variable's value.

2. Step 2: Compare with other options

   Declaring variables, repeating a block of code multiple times, and defining a function are not the purpose of switch.

3. Final Answer:

   To choose between multiple actions based on the value of a variable -> Option B

4. Quick Check:

   switch selects code by value [OK]

Hint: Switch picks code based on variable value, like a menu choice [OK]

Common Mistakes:

• Confusing switch with loops
• Thinking switch declares variables
• Using switch to define functions

2. Which of the following is the correct syntax to start a switch statement in C?

easy

A. switch(variable) {

B. switch variable {

C. switch variable() {

D. switch { variable }

Solution

1. Step 1: Recall correct switch syntax

   The correct syntax requires the keyword switch followed by parentheses enclosing the variable, then an opening brace.

2. Step 2: Check each option

   switch(variable) { matches the correct syntax: switch(variable) {. Others miss parentheses or use wrong braces.

3. Final Answer:

   switch(variable) { -> Option A

4. Quick Check:

   Syntax needs parentheses around variable [OK]

Hint: Remember: switch(variable) with parentheses and braces [OK]

Common Mistakes:

• Omitting parentheses around variable
• Using wrong braces or brackets
• Adding parentheses after variable name

3. What will be the output of the following C code?

int x = 2;
switch(x) {
  case 1:
    printf("One\n");
    break;
  case 2:
    printf("Two\n");
    break;
  default:
    printf("Other\n");
}

medium

A. One

B. Other

C. Two

D. No output

Solution

1. Step 1: Identify the value of variable x

   The variable x is set to 2.

2. Step 2: Match x with case labels

   The switch checks cases: 1 and 2. Since x is 2, it matches case 2 and prints "Two".

3. Final Answer:

   Two -> Option C

4. Quick Check:

   Value 2 matches case 2 [OK]

Hint: Match variable value to case label to find output [OK]

Common Mistakes:

• Ignoring break and falling through
• Choosing default when case matches
• Confusing case numbers

4. Identify the error in this switch statement:

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

medium

A. Missing break after case 1 causes fall-through

B. Variable n is not declared

C. Default case must be first

D. Switch cannot use integers

Solution

1. Step 1: Check for break statements

   Case 1 lacks a break, so after printing "One", execution continues to case 2.

2. Step 2: Understand consequences of missing break

   This fall-through causes both "One" and "Two" to print when n is 1, which is usually unintended.

3. Final Answer:

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

4. Quick Check:

   Always add break to prevent fall-through [OK]

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

Common Mistakes:

• Forgetting break after cases
• Thinking default must be first
• Believing switch can't use integers

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

hard

A. switch(day) {
if(day >= 1 && day <= 5) {
printf("Weekday\n");
} else if(day == 6 || day == 7) {
printf("Weekend\n");
} else {
printf("Invalid\n");
}
}

B. switch(day) {
case 1:
printf("Weekday\n");
case 2:
printf("Weekday\n");
case 3:
printf("Weekday\n");
case 4:
printf("Weekday\n");
case 5:
printf("Weekday\n");
case 6:
printf("Weekend\n");
case 7:
printf("Weekend\n");
default:
printf("Invalid\n");
}

C. switch(day) {
case 1 ... 5:
printf("Weekday\n");
break;
case 6 ... 7:
printf("Weekend\n");
break;
default:
printf("Invalid\n");
}

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

Solution

1. Step 1: Understand valid switch syntax for multiple cases

   Cases can be grouped by listing them one after another without breaks to share code.

2. Step 2: Evaluate each option

   switch(day) { case 1: case 2: case 3: case 4: case 5: printf("Weekday\n"); break; case 6: case 7: printf("Weekend\n"); break; default: printf("Invalid\n"); } correctly groups cases 1 to 5 and 6 to 7, with breaks and a default. switch(day) { case 1: printf("Weekday\n"); case 2: printf("Weekday\n"); case 3: printf("Weekday\n"); case 4: printf("Weekday\n"); case 5: printf("Weekday\n"); case 6: printf("Weekend\n"); case 7: printf("Weekend\n"); default: printf("Invalid\n"); } lacks breaks causing fall-through. switch(day) { case 1 ... 5: printf("Weekday\n"); break; case 6 ... 7: printf("Weekend\n"); break; default: printf("Invalid\n"); } uses invalid syntax (case 1 ... 5). switch(day) { if(day >= 1 && day <= 5) { printf("Weekday\n"); } else if(day == 6 || day == 7) { printf("Weekend\n"); } else { printf("Invalid\n"); } } uses if inside switch without case labels, making the body unreachable and invalid for switch logic.

3. Final Answer:

   Groups cases by listing consecutive cases for shared execution with breaks -> Option D

4. Quick Check:

   Group cases by listing them, add breaks [OK]

Hint: Group cases by listing them; use breaks to separate [OK]

Common Mistakes:

• Using invalid range syntax in case
• Missing breaks causing fall-through
• Trying to use if inside switch