Solving linear systems (A\b) in MATLAB - Time & Space Complexity

Time Complexity: Solving linear systems (A\b)

O(n^3)

Understanding Time Complexity

When solving linear systems using A\b in MATLAB, it's important to know how the time needed grows as the system size increases.

We want to understand how the work changes when the matrix gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    n = 1000;
    A = rand(n);
    b = rand(n,1);
    x = A \ b;
    

This code creates a random square matrix A and vector b, then solves for x in the equation A*x = b.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matrix factorization and back substitution steps inside A\b.
• How many times: These steps involve nested loops over the matrix size, roughly repeating n times inside n times.

How Execution Grows With Input

As the matrix size n grows, the number of operations grows much faster because each element interacts with many others.

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

Pattern observation: When n increases ten times, operations increase about a thousand times, showing a cubic growth.

Final Time Complexity

Time Complexity: O(n^3)

This means the time needed grows roughly with the cube of the matrix size, so doubling n makes the work about eight times bigger.

Common Mistake

[X] Wrong: "Solving A\b takes time proportional to n, like a simple loop."

[OK] Correct: The solution involves nested operations on the matrix, not just one pass, so it grows much faster than n.

Interview Connect

Understanding how solving linear systems scales helps you explain performance in real tasks like simulations or data analysis, showing you know how algorithms behave with bigger data.

Self-Check

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

Practice

1. What does the MATLAB expression x = A\b do?

easy

A. Solves the linear system Ax = b for x

B. Calculates the inverse of matrix A

C. Multiplies matrix A by vector b

D. Transposes matrix A and multiplies by b

Solution

1. Step 1: Understand the expression A\b

   The operator \ in MATLAB is used to solve linear systems of the form Ax = b.

2. Step 2: Identify the purpose of A\b

   It finds the vector x that satisfies the equation Ax = b without explicitly calculating the inverse of A.

3. Final Answer:

   Solves the linear system Ax = b for x -> Option A

4. Quick Check:

   A\b solves Ax = b [OK]

Hint: Remember: A\b solves Ax = b directly [OK]

Common Mistakes:

• Confusing A\b with matrix multiplication
• Thinking it calculates inverse of A
• Using b\A instead of A\b

2. Which of the following is the correct syntax to solve the system Ax = b in MATLAB?

easy

A. x = A\b;

B. x = b/A;

C. x = inv(A)\b;

D. x = A*b;

Solution

1. Step 1: Recall MATLAB syntax for solving linear systems

   The correct syntax uses the backslash operator: x = A\b;

2. Step 2: Check other options for correctness

   x = b/A; uses b/A which is incorrect; x = inv(A)\b; uses inv(A)\b which solves inv(A)x = b (wrong system); x = A*b; multiplies A and b which is not solving the system.

3. Final Answer:

   x = A\b; -> Option A

4. Quick Check:

   Use backslash operator for solving Ax = b [OK]

Hint: Use backslash \ operator, not division or inverse [OK]

Common Mistakes:

• Using b/A instead of A\b
• Using inv(A)\b which solves wrong system
• Confusing multiplication with solving

3. Given A = [2 1; 3 4] and b = [5; 10], what is the result of x = A\b?

medium

A. [1; 2]

B. [5; 6]

C. [0; 0]

D. [2; 1]

Solution

1. Step 1: Write the system of equations

   2x1 + x2 = 5
   3x1 + 4x2 = 10.

2. Step 2: Solve using elimination

   Multiply first equation by 4: 8x1 + 4x2 = 20.
   Subtract second: 5x1 = 10 -> x1 = 2.
   Substitute: x2 = 5 - 2*2 = 1.

3. Step 3: Verify solution

   A*[2; 1] = [2*2 + 1*1; 3*2 + 4*1] = [5; 10] = b.

4. Final Answer:

   [2; 1] -> Option D

5. Quick Check:

   A\b = [2; 1] [OK]

Hint: Use A\b to get exact solution vector [OK]

Common Mistakes:

• Miscalculating substitution (e.g., picking [1; 2])
• Confusing with matrix multiplication A*b
• Selecting x = b

4. What is wrong with this MATLAB code snippet?

A = [1 2; 3 4];
b = [5; 6; 7];
x = A\b;

medium

A. Backslash operator cannot solve linear systems

B. Matrix A and vector b have incompatible dimensions

C. Missing semicolon after assignment

D. Matrix A is not square

Solution

1. Step 1: Check dimensions of A and b

   Matrix A is 2x2, vector b is 3x1. For Ax = b, number of rows in A must equal length of b.

2. Step 2: Identify dimension mismatch

   Since A has 2 rows but b has 3 elements, dimensions are incompatible, causing an error when solving.

3. Final Answer:

   Matrix A and vector b have incompatible dimensions -> Option B

4. Quick Check:

   Rows of A must match length of b [OK]

Hint: Check matrix and vector sizes before solving [OK]

Common Mistakes:

• Ignoring dimension mismatch errors
• Thinking backslash works for any sizes
• Assuming A must be square always

5. You have a non-square matrix A = [1 2 3; 4 5 6] and vector b = [7; 8]. What does x = A\b compute in MATLAB?

hard

A. The inverse of A times b

B. An error because A is not square

C. A least-squares solution minimizing ||Ax - b||

D. A random vector x

Solution

1. Step 1: Recognize matrix shape and operation

   A is 2x3 (more columns than rows), so system is underdetermined.

2. Step 2: Understand MATLAB's backslash behavior for non-square A

   MATLAB computes the least-squares solution x that minimizes ||Ax - b|| (minimum norm among solutions).

3. Final Answer:

   A least-squares solution minimizing ||Ax - b|| -> Option C

4. Quick Check:

   Backslash solves least-squares for non-square A [OK]

Hint: Backslash gives least-squares solution if A not square [OK]

Common Mistakes:

• Expecting error for non-square A
• Thinking it calculates inverse always
• Assuming exact solution always exists