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?"

Practice

1. What does it mean when one object calls a method on another object in C++?

easy

A. The first object is asking the second object to perform an action.

B. The first object copies the second object's data.

C. The first object deletes the second object.

D. The first object creates a new object inside the second object.

Solution

1. Step 1: Understand method calls between objects

   When one object calls a method on another, it requests that object to do something or provide information.

2. Step 2: Differentiate from other actions

   Copying data, deleting, or creating objects are different operations, not the same as calling a method.

3. Final Answer:

   The first object is asking the second object to perform an action. -> Option A

4. Quick Check:

   Object method call = request action [OK]

Hint: Method call means asking another object to do something [OK]

Common Mistakes:

• Confusing method call with copying data
• Thinking method call deletes objects
• Assuming method call creates new objects inside others

2. Which of the following is the correct syntax to pass an object obj of class Car to a method drive of another object driver?

easy

A. driver.drive(obj);

B. drive.driver(obj);

C. driver->drive(obj);

D. drive(obj).driver;

Solution

1. Step 1: Identify correct method call syntax

   For an object driver, calling method drive with argument obj uses dot notation: driver.drive(obj);

2. Step 2: Eliminate incorrect syntax

   drive.driver(obj); reverses object and method, driver->drive(obj); is for pointers, and drive(obj).driver; is invalid.

3. Final Answer:

   driver.drive(obj); -> Option A

4. Quick Check:

   Object.method(argument) = driver.drive(obj) [OK]

Hint: Use object.method(argument) syntax for calling methods [OK]

Common Mistakes:

• Using arrow operator on non-pointer objects
• Swapping method and object names
• Incorrect punctuation or order

3. What is the output of this code?

#include <iostream>

class Light {
public:
    void turnOn() { std::cout << "Light is ON" << std::endl; }
};

class Switch {
public:
    void press(Light &l) { l.turnOn(); }
};

int main() {
    Light roomLight;
    Switch wallSwitch;
    wallSwitch.press(roomLight);
    return 0;
}

medium

A. Compilation error

B. Light is OFF

C. No output

D. Light is ON

Solution

1. Step 1: Understand method call inside press()

   The press method calls turnOn() on the passed Light object, which prints "Light is ON".

2. Step 2: Trace main function calls

   wallSwitch.press(roomLight); calls turnOn() on roomLight, so output is "Light is ON".

3. Final Answer:

   Light is ON -> Option D

4. Quick Check:

   Method call prints "Light is ON" [OK]

Hint: Method calls inside other methods print output [OK]

Common Mistakes:

• Assuming no output because press() returns void
• Confusing reference passing with copying
• Thinking code causes compilation error

4. Identify the error in this code snippet:

#include <iostream>

class Engine {
public:
    void start() { std::cout << "Engine started" << std::endl; }
};

class Car {
public:
    void ignite(Engine e) { e.start(); }
};

int main() {
    Engine myEngine;
    Car myCar;
    myCar.ignite(myEngine);
    return 0;
}

medium

A. Method start() is not declared correctly.

B. Car class should inherit from Engine.

C. Passing Engine by value causes unnecessary copying.

D. Cannot call start() on Engine object.

Solution

1. Step 1: Analyze parameter passing in ignite()

   The method ignite takes Engine e by value, which copies the object unnecessarily.

2. Step 2: Suggest improvement

   Passing by reference (Engine &e) avoids copying and is more efficient.

3. Final Answer:

   Passing Engine by value causes unnecessary copying. -> Option C

4. Quick Check:

   Pass objects by reference to avoid copying [OK]

Hint: Pass objects by reference to avoid copies [OK]

Common Mistakes:

• Thinking method start() is incorrect
• Assuming inheritance is required
• Believing start() cannot be called on Engine

5. Given classes Teacher and Student, how can you design a method in Teacher that lets a teacher assign a grade to a student object? Choose the best approach.

hard

A. Make Student inherit from Teacher and override a grade method.

B. Define a method in Teacher that takes a Student reference and an int grade, then calls a Student method to set the grade.

C. Store grades only inside Teacher without involving Student objects.

D. Use global variables to store grades for all students.

Solution

1. Step 1: Understand object interaction for assigning grades

   The Teacher should interact with Student by calling a method on Student to set the grade, passing the grade value.

2. Step 2: Evaluate options

   Define a method in Teacher that takes a Student reference and an int grade, then calls a Student method to set the grade. correctly uses a method in Teacher that takes a Student reference and grade, then calls Student's method to set the grade. Other options misuse inheritance, ignore object interaction, or use bad global state.

3. Final Answer:

   Define a method in Teacher that takes a Student reference and an int grade, then calls a Student method to set the grade. -> Option B

4. Quick Check:

   Teacher calls Student method to assign grade [OK]

Hint: Teacher calls Student method with grade parameter [OK]

Common Mistakes:

• Misusing inheritance for unrelated roles
• Ignoring encapsulation by using globals
• Storing grades only in Teacher without Student update