Template literal with unions in Typescript - Time & Space Complexity

Time Complexity: Template literal with unions

O(n * m)

Understanding Time Complexity

We want to understand how the time it takes to create strings using template literals with unions changes as the input size grows.

Specifically, how does the number of possible string combinations affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

type Colors = "red" | "green" | "blue";
type Sizes = "small" | "medium" | "large";

type Shirt = `${Colors}-${Sizes}`;

function getAllShirts(): Shirt[] {
  const colors: Colors[] = ["red", "green", "blue"];
  const sizes: Sizes[] = ["small", "medium", "large"];
  const shirts: Shirt[] = [];

  for (const color of colors) {
    for (const size of sizes) {
      shirts.push(`${color}-${size}` as Shirt);
    }
  }
  return shirts;
}
    

This code creates all possible shirt descriptions by combining colors and sizes using template literals with union types.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over colors and sizes arrays.
• How many times: Outer loop runs once per color, inner loop runs once per size, total runs = colors x sizes.

How Execution Grows With Input

As the number of colors and sizes grows, the total combinations grow by multiplying these counts.

Input Size (colors x sizes)	Approx. Operations
10 (e.g., 5 colors x 2 sizes)	10 string creations
100 (e.g., 10 colors x 10 sizes)	100 string creations
1000 (e.g., 20 colors x 50 sizes)	1000 string creations

Pattern observation: The work grows proportionally to the product of the input sizes.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the number of colors times the number of sizes.

Common Mistake

[X] Wrong: "The time grows only with the number of colors or sizes, not both."

[OK] Correct: Because the code combines every color with every size, the total work depends on both inputs multiplied together, not just one.

Interview Connect

Understanding how nested loops multiply work helps you explain performance clearly and shows you can reason about combinations in code.

Self-Check

"What if we added a third union type for styles and nested another loop? How would the time complexity change?"