Capitalize and Uncapitalize types in Typescript - Time & Space Complexity

Time Complexity: Capitalize and Uncapitalize types

O(1)

Understanding Time Complexity

We want to understand how the time needed to run code changes when using Capitalize and Uncapitalize types in TypeScript.

Specifically, how does the work grow as the input string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

type Capitalized = Capitalize<"hello">;
type Uncapitalized = Uncapitalize<"World">;

// Using template literal types to capitalize first letter

type CapitalizeString<S extends string> = S extends `${infer F}${infer R}` ? `${Uppercase<F>}${R}` : S;

// Using template literal types to uncapitalize first letter

type UncapitalizeString<S extends string> = S extends `${infer F}${infer R}` ? `${Lowercase<F>}${R}` : S;

This code defines types that change the first letter of a string to uppercase or lowercase.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: TypeScript checks the first character of the string and changes its case.
• How many times: Only once per string type, no loops or recursion over the whole string.

How Execution Grows With Input

The operation only looks at the first letter, so the time does not grow with the string length.

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

Pattern observation: The work stays the same no matter how long the string is.

Final Time Complexity

Time Complexity: O(1)

This means the time to capitalize or uncapitalize is constant and does not depend on the string length.

Common Mistake

[X] Wrong: "Changing the case of a string type takes longer for longer strings because it processes every character."

[OK] Correct: The type only changes the first character and leaves the rest unchanged, so it does not process the whole string.

Interview Connect

Understanding how TypeScript handles string manipulation types helps you reason about type-level programming and its efficiency, a useful skill in advanced TypeScript coding.

Self-Check

"What if we changed the type to capitalize every letter in the string? How would the time complexity change?"