States and transitions in Simulink - Time & Space Complexity

Time Complexity: States and transitions

O(n)

Understanding Time Complexity

We want to understand how the time to run a state machine in Simulink grows as the number of states and transitions increases.

How does adding more states or transitions affect the work the model does?

Scenario Under Consideration

Analyze the time complexity of the following state machine logic.

  % Pseudocode for a state machine in Simulink
  currentState = initialState;
  while running
    for each transition in transitionsFrom(currentState)
      if conditionMet(transition)
        currentState = transition.nextState;
        break;
      end
    end
  end
    

This code checks all possible transitions from the current state to decide the next state.

Identify Repeating Operations

Look at what repeats as the model runs.

• Primary operation: Checking each transition from the current state.
• How many times: For each step, it loops over all transitions from that state.

How Execution Grows With Input

As the number of states and transitions grows, the checks increase.

Input Size (number of transitions from current state)	Approx. Operations per step
10	About 10 transition checks
100	About 100 transition checks
1000	About 1000 transition checks

Pattern observation: The number of checks grows roughly in direct proportion to the number of transitions from the current state.

Final Time Complexity

Time Complexity: O(n)

This means the time to decide the next state grows linearly with the number of transitions from the current state.

Common Mistake

[X] Wrong: "The time to find the next state stays the same no matter how many states or transitions there are."

[OK] Correct: More transitions mean more conditions to check, so the time grows with the number of transitions.

Interview Connect

Understanding how state machines scale helps you design efficient models and explain your reasoning clearly in discussions.

Self-Check

"What if we stored transitions in a way that lets us jump directly to the correct one without checking all? How would the time complexity change?"

Practice

1. In Simulink Stateflow, what does a state represent?

easy

A. A mathematical operation

B. A graphical icon only

C. A data storage variable

D. A mode or condition of the system

Solution

1. Step 1: Understand the role of states in Stateflow

   States represent different modes or conditions that a system can be in during execution.

2. Step 2: Differentiate states from other elements

   States are not variables or operations; they define behavior and system modes.

3. Final Answer:

   A mode or condition of the system -> Option D

4. Quick Check:

   State = system mode [OK]

Hint: States = system modes or conditions [OK]

Common Mistakes:

• Confusing states with variables
• Thinking states are just icons
• Mixing states with mathematical operations

2. Which of the following is the correct syntax to define a transition condition in Simulink Stateflow?

easy

A. state1 => state2 (condition)

B. state1 -> state2 {condition}

C. state1 --> state2 [condition]

D. state1 -- state2 [condition]

Solution

1. Step 1: Recall Stateflow transition syntax

   Transitions use the arrow --> followed by a condition in square brackets.

2. Step 2: Match syntax options

   state1 --> state2 [condition] uses --> and square brackets correctly, others use incorrect symbols or brackets.

3. Final Answer:

   state1 --> state2 [condition] -> Option C

4. Quick Check:

   Transition syntax = --> [condition] [OK]

Hint: Transitions use --> with [condition] brackets [OK]

Common Mistakes:

• Using wrong arrow symbols
• Using curly or round brackets instead of square
• Omitting the condition brackets

3. Given this Stateflow snippet:

state A
  entry: x = 0;
  during: x = x + 1;
end

transition from A to B [x >= 3]

What is the value of x when the system transitions from state A to B?

medium

A. 3

B. 4

C. 2

D. 0

Solution

1. Step 1: Analyze state A behavior

   On entry, x is set to 0. During state A, x increments by 1 each cycle.

2. Step 2: Determine when transition triggers

   Transition triggers when x >= 3. So after 3 increments, x equals 3 and transition occurs.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Transition at x >= 3 means x = 3 [OK]

Hint: Transition triggers when condition first becomes true [OK]

Common Mistakes:

• Counting increments before entry action
• Assuming transition triggers at x > 3 instead of >= 3
• Forgetting initial value of x

4. Identify the error in this transition definition:

state A
end
state B
end

A --> B (x > 5)

medium

A. Missing condition brackets [] around (x > 5)

B. Incorrect arrow symbol used

C. States must have entry actions

D. Transition must be inside state definitions

Solution

1. Step 1: Check transition condition syntax

   Transition conditions must be enclosed in square brackets [], not parentheses ().

2. Step 2: Verify other syntax elements

   The arrow --> is correct, states can be empty, and transitions are defined outside states.

3. Final Answer:

   Missing condition brackets [] around (x > 5) -> Option A

4. Quick Check:

   Conditions use [] not () [OK]

Hint: Use [] for conditions, not () [OK]

Common Mistakes:

• Using parentheses instead of square brackets
• Thinking arrow is wrong
• Believing states must have actions

5. You want to model a traffic light system with states Red, Green, and Yellow. The system should transition from Green to Yellow only if a timer reaches 60 seconds. Which transition condition correctly models this?

hard

A. Green --> Yellow [timer > 60]

B. Green --> Yellow [timer == 60]

C. Green --> Yellow [timer < 60]

D. Green --> Yellow [timer != 60]

Solution

1. Step 1: Understand the timing condition

   The transition should happen exactly when the timer reaches 60 seconds, so the condition must check equality.

2. Step 2: Evaluate options

   Green --> Yellow [timer == 60] uses timer == 60, which triggers transition at 60 seconds. Others check greater, less, or not equal, which do not match the requirement.

3. Final Answer:

   Green --> Yellow [timer == 60] -> Option B

4. Quick Check:

   Exact timer match triggers transition [OK]

Hint: Use == for exact timer match in transitions [OK]

Common Mistakes:

• Using > or < instead of ==
• Using != which triggers at wrong times
• Forgetting square brackets around condition