Real-world modeling in C++ - Time & Space Complexity

Time Complexity: Real-world modeling

O(n²)

Understanding Time Complexity

When we model real-world problems in code, we want to know how long our program takes as the problem grows.

We ask: How does the work increase when the input gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <vector>
#include <iostream>

void printPairs(const std::vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = 0; j < nums.size(); ++j) {
            std::cout << nums[i] << "," << nums[j] << std::endl;
        }
    }
}
    

This code prints all pairs of numbers from the input list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops printing pairs of elements.
• How many times: Outer loop runs n times; inner loop runs n times for each outer loop.

How Execution Grows With Input

As the input size grows, the number of pairs grows much faster.

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

Pattern observation: Doubling the input size makes the work about four times bigger.

Final Time Complexity

Time Complexity: O(n²)

This means the work grows by the square of the input size; twice the input means about four times the work.

Common Mistake

[X] Wrong: "Since there are two loops, the time is just twice as long as input size."

[OK] Correct: The loops are nested, so the inner loop runs fully for each outer loop step, multiplying the work, not adding.

Interview Connect

Understanding how nested loops affect time helps you explain your code clearly and shows you can think about efficiency in real problems.

Self-Check

"What if we changed the inner loop to run only from j = i to the end? How would the time complexity change?"