Object interaction in C++ - Time & Space Complexity

Time Complexity: Object interaction

O(n)

Understanding Time Complexity

When objects work together in a program, it's important to know how the time needed grows as we add more objects.

We want to find out how the number of interactions affects the total work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Item {
public:
    void interact() {
        // some simple operation
    }
};

void processItems(std::vector<Item>& items) {
    for (auto &item : items) {
        item.interact();
    }
}
    

This code calls a method on each object in a list, making each object do some work once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling interact() on each object.
• How many times: Once for each object in the list.

How Execution Grows With Input

As the number of objects grows, the total work grows in a straight line.

Input Size (n)	Approx. Operations
10	10 calls to interact()
100	100 calls to interact()
1000	1000 calls to interact()

Pattern observation: Doubling the number of objects doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly with the number of objects.

Common Mistake

[X] Wrong: "Calling a method on each object is constant time no matter how many objects there are."

[OK] Correct: Each object adds more work, so total time grows with the number of objects.

Interview Connect

Understanding how objects interact and how that affects time helps you explain your code clearly and shows you think about efficiency.

Self-Check

"What if each interact() method called another loop over all objects? How would the time complexity change?"