Nested loops in MATLAB - Time & Space Complexity

Time Complexity: Nested loops

O(n^2)

Understanding Time Complexity

When we use nested loops, the program repeats actions inside another repeated action. This can make the program take longer as the input grows.

We want to know how much longer the program takes when the input size gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

n = 5;
for i = 1:n
    for j = 1:n
        disp(i * j);
    end
end

This code prints the product of two numbers for every pair from 1 to n, using two loops inside each other.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop runs a print command for each pair (i, j).
• How many times: The outer loop runs n times, and for each outer loop, the inner loop runs n times, so total n x n times.

How Execution Grows With Input

As n grows, the total number of print actions grows by n times n.

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

Pattern observation: When n doubles, the operations become about four times more, showing a square growth.

Final Time Complexity

Time Complexity: O(n^2)

This means the time it takes grows roughly with the square of the input size.

Common Mistake

[X] Wrong: "The inner loop only adds a little extra time, so the total time is just twice as long as one loop."

[OK] Correct: Because the inner loop runs completely for each outer loop step, the total work multiplies, not just adds.

Interview Connect

Understanding nested loops helps you explain how programs handle repeated tasks inside other repeated tasks, a common pattern in coding challenges and real projects.

Self-Check

"What if the inner loop ran only half as many times as the outer loop? How would the time complexity change?"