Discriminated union state machines in Typescript - Time & Space Complexity

Time Complexity: Discriminated union state machines

O(1)

Understanding Time Complexity

When using discriminated union state machines, it's important to know how the program's steps grow as the input changes.

We want to see how the number of operations changes when the machine processes different inputs.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    type State =
      | { type: 'idle' }
      | { type: 'loading' }
      | { type: 'success'; data: string[] }
      | { type: 'error'; message: string };

    function processState(state: State): number {
      switch (state.type) {
        case 'idle':
          return 0;
        case 'loading':
          return 1;
        case 'success':
          return state.data.length;
        case 'error':
          return -1;
      }
    }
    

This code checks the state type and returns a number based on the state, counting items if successful.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing state.data.length when state is 'success'.
• How many times: Exactly once per function call, no loops or recursion inside.

How Execution Grows With Input

The function does a simple check and returns a value. The only input-dependent step is reading the length of an array.

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

Pattern observation: The number of operations stays the same no matter how big the data array is.

Final Time Complexity

Time Complexity: O(1)

This means the function runs in constant time, doing the same amount of work regardless of input size.

Common Mistake

[X] Wrong: "Because the data array can be large, the function takes longer to run."

[OK] Correct: The function only reads the length property, which is stored and accessed instantly, so size doesn't affect time.

Interview Connect

Understanding how state machines handle inputs efficiently shows you can write clear and fast code, a skill valued in many coding challenges.

Self-Check

"What if the function had to sum all numbers in the data array instead of just reading its length? How would the time complexity change?"