Why numerical computation solves real problems in MATLAB - Performance Analysis

Time Complexity: Why numerical computation solves real problems

O(n)

Understanding Time Complexity

When we use numerical computation, we want to know how long it takes as the problem gets bigger.

We ask: How does the work grow when the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function result = sumSquares(n)
    result = 0;
    for i = 1:n
        result = result + i^2;
    end
end
    

This code adds up the squares of numbers from 1 to n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding the square of each number to the total.
• How many times: The loop runs once for each number from 1 to n, so n times.

How Execution Grows With Input

As n gets bigger, the number of additions grows the same way.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: The work grows directly with n; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the size of the input.

Common Mistake

[X] Wrong: "Since we do a calculation inside the loop, the time grows faster than n."

[OK] Correct: Each calculation inside the loop takes about the same time, so the total time still grows just like n.

Interview Connect

Understanding how numerical computations scale helps you explain your code's efficiency clearly and confidently.

Self-Check

"What if we used two nested loops to sum squares for pairs of numbers? How would the time complexity change?"