State diagrams in Software Engineering - Time & Space Complexity

Time Complexity: State diagrams

O(n)

Understanding Time Complexity

State diagrams help us understand how a system moves between different states based on events.

We want to see how the time to process inputs grows as the number of states or transitions increases.

Scenario Under Consideration

Analyze the time complexity of processing an input event in a state machine.

class StateMachine:
    def __init__(self, transitions):
        self.transitions = transitions  # dict: (state, event) -> new_state
        self.current_state = 'start'

    def handle_event(self, event):
        key = (self.current_state, event)
        if key in self.transitions:
            self.current_state = self.transitions[key]
        return self.current_state
    

This code moves the machine from one state to another based on the current state and an event.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking if a (state, event) pair exists in the transitions dictionary.
• How many times: Once per event handled.

How Execution Grows With Input

Each event causes one lookup to find the next state.

Input Size (n)	Approx. Operations
10 events	10 lookups
100 events	100 lookups
1000 events	1000 lookups

Pattern observation: The number of operations grows directly with the number of events processed.

Final Time Complexity

Time Complexity: O(n)

This means processing n events takes time proportional to n, with each event handled quickly.

Common Mistake

[X] Wrong: "The time to find the next state grows with the number of states or transitions."

[OK] Correct: Using a dictionary for transitions means each lookup is very fast and does not slow down as the number of states grows.

Interview Connect

Understanding how state machines handle events efficiently shows you can reason about system behavior and performance, a useful skill in many software roles.

Self-Check

What if the transitions were stored in a list instead of a dictionary? How would the time complexity change?