Relational expressions in MATLAB - Time & Space Complexity

Time Complexity: Relational expressions

O(n)

Understanding Time Complexity

Relational expressions compare values and return true or false. We want to see how the time to evaluate these expressions changes as input size grows.

How does the number of comparisons grow when we check many values?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

A = rand(1, n);  % Create an array of n random numbers
count = 0;
for i = 1:n
    if A(i) > 0.5
        count = count + 1;
    end
end

This code counts how many numbers in the array are greater than 0.5 using a relational expression inside a loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The relational check A(i) > 0.5 inside the loop.
• How many times: This check runs once for each element, so n times.

How Execution Grows With Input

Each new element adds one more comparison. So if you double the input size, you double the work.

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

Pattern observation: The number of operations grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the input gets bigger.

Common Mistake

[X] Wrong: "Relational expressions inside loops run in constant time no matter the input size."

[OK] Correct: Each relational check happens once per element, so more elements mean more checks and more time.

Interview Connect

Understanding how simple comparisons add up helps you explain how your code scales. This skill shows you can think about efficiency clearly.

Self-Check

"What if we replaced the loop with a vectorized relational expression? How would the time complexity change?"