Discrete state-space in Simulink - Time & Space Complexity

Time Complexity: Discrete state-space

O(n^2)

Understanding Time Complexity

We want to understand how the time needed to run a discrete state-space model changes as the size of the system grows.

How does the number of calculations grow when we increase the number of states?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

% Discrete state-space update
x_next = A * x + B * u;
y = C * x + D * u;
x = x_next;
    

This code updates the system state and output at each time step using matrix multiplication.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matrix multiplication of A by x and C by x.
• How many times: Once per time step, repeated for each update.

How Execution Grows With Input

As the number of states (n) grows, the number of calculations grows roughly with the square of n because of matrix multiplication.

Input Size (n)	Approx. Operations
10	About 100 operations
100	About 10,000 operations
1000	About 1,000,000 operations

Pattern observation: When n increases ten times, operations increase about one hundred times.

Final Time Complexity

Time Complexity: O(n2)

This means the time to update the state grows roughly with the square of the number of states.

Common Mistake

[X] Wrong: "The time grows linearly with the number of states because we just update each state once."

[OK] Correct: Each state update involves multiplying matrices, which requires combining all states together, causing the time to grow faster than just counting states.

Interview Connect

Understanding how matrix operations affect time helps you explain performance in control systems and simulations clearly and confidently.

Self-Check

"What if the matrix A was sparse (mostly zeros)? How would the time complexity change?"

Practice

1. What does a discrete state-space model in Simulink primarily represent?

easy

A. A continuous-time system with differential equations

B. A graphical user interface for designing circuits

C. A system described by matrices that updates states step-by-step

D. A tool for creating 3D animations

Solution

1. Step 1: Understand discrete state-space concept

   Discrete state-space models describe systems using matrices that update the system's state at each time step.

2. Step 2: Compare options

   Only a system described by matrices that updates states step-by-step correctly describes this concept; others describe unrelated tools or continuous systems.

3. Final Answer:

   A system described by matrices that updates states step-by-step -> Option C

4. Quick Check:

   Discrete state-space = step-by-step matrix system [OK]

Hint: Discrete means step-by-step matrix updates [OK]

Common Mistakes:

• Confusing discrete with continuous systems
• Thinking state-space is only for continuous models
• Mixing up state-space with graphical tools

2. Which of the following is the correct syntax to define a discrete state-space system in Simulink's MATLAB Function block?

easy

A. sys = ss(A, B, C, D);

B. sys = ss(A, B, C, D, Ts);

C. sys = discrete(A, B, C, D, Ts);

D. sys = state_space(A, B, C, D, Ts);

Solution

1. Step 1: Recall syntax for discrete state-space

   In MATLAB/Simulink, discrete state-space systems use ss(A,B,C,D,Ts) where Ts is the sample time.

2. Step 2: Evaluate options

   sys = ss(A, B, C, D, Ts); matches the correct syntax. sys = ss(A, B, C, D); misses Ts (sample time), C and D use incorrect function names.

3. Final Answer:

   sys = ss(A, B, C, D, Ts); -> Option B

4. Quick Check:

   Discrete ss needs sample time Ts [OK]

Hint: Discrete ss needs sample time Ts as last argument [OK]

Common Mistakes:

• Omitting the sample time Ts
• Using wrong function names like discrete()
• Confusing continuous and discrete syntax

3. Given the discrete state-space matrices:
A = [[0.7, 0.2], [0, 0.9]];
B = [[0.1], [0.05]];
and initial state x0 = [1; 0], what is the state x[1] after one step with input u[0] = 2?

medium

A. [1.6; 0.1]

B. [1.0; 0.05]

C. [1.8; 0.0]

D. [0.9; 0.1]

Solution

1. Step 1: Calculate next state using formula

   Next state x[1] = A * x0 + B * u[0]. Calculate:
   A * x0 = [0.7*1 + 0.2*0; 0*1 + 0.9*0] = [0.7; 0]
   B * u[0] = [0.1*2; 0.05*2] = [0.2; 0.1]

2. Step 2: Add results to get x[1]

   x[1] = [0.7; 0] + [0.2; 0.1] = [0.9; 0.1]

3. Final Answer:

   [0.9; 0.1] -> Option D

4. Quick Check:

   Use x[1] = A*x0 + B*u[0] [OK]

Hint: Multiply A*x0 and add B*u[0] for next state [OK]

Common Mistakes:

• Forgetting to multiply input u by B
• Mixing matrix multiplication order
• Adding instead of multiplying matrices

4. You have this discrete state-space model in Simulink:
A = [[1, 0], [0, 1]];
B = [[0], [0]];
C = [[1, 0]];
D = [[0]];
Why does the output never change regardless of input?

medium

A. Because matrix B is zero, input has no effect on state

B. Because matrix C is zero, output is always zero

C. Because matrix A is identity, states never update

D. Because matrix D is zero, output ignores input

Solution

1. Step 1: Analyze matrix B effect on input

   Matrix B is zero, so input u does not affect state update: x[k+1] = A*x[k] + B*u[k] = A*x[k].

2. Step 2: Understand output behavior

   Output y = C*x + D*u depends only on state x and input u. Since input doesn't change state, output depends only on initial state and does not change with input.

3. Final Answer:

   Because matrix B is zero, input has no effect on state -> Option A

4. Quick Check:

   Zero B means input can't change state [OK]

Hint: Zero B means input can't change state [OK]

Common Mistakes:

• Confusing zero D with zero B effect
• Assuming identity A means output changes
• Ignoring input effect on state update

5. You want to design a discrete state-space model in Simulink to simulate a system with states updated every 0.1 seconds. The system matrices are:
A = [[0.8, 0.1], [0, 0.9]];
B = [[0.05], [0.02]];
Which sample time should you specify to correctly model this system?

hard

A. 0.1

B. 1

C. 0

D. -0.1

Solution

1. Step 1: Understand sample time meaning

   Sample time Ts defines how often the discrete system updates its state. Here, states update every 0.1 seconds.

2. Step 2: Choose correct sample time

   Ts must be positive and equal to the update interval, so Ts = 0.1 seconds.

3. Final Answer:

   0.1 -> Option A

4. Quick Check:

   Sample time = update interval = 0.1 [OK]

Hint: Sample time equals system update interval (positive) [OK]

Common Mistakes:

• Using zero or negative sample time
• Confusing sample time with continuous time
• Choosing wrong units for sample time