Interface-like behavior in C++ - Time & Space Complexity

Time Complexity: Interface-like behavior

O(n)

Understanding Time Complexity

When we use interface-like behavior in C++, we often call functions through pointers or references to base classes. This can affect how long the program takes to run.

We want to know how the time to run changes when we call methods this way.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Shape {
public:
    virtual void draw() {}
};

class Circle : public Shape {
public:
    void draw() override {
        // drawing circle
    }
};

void drawAllShapes(std::vector<Shape*> shapes) {
    for (auto shape : shapes) {
        shape->draw();
    }
}
    

This code calls the draw method on each shape using interface-like behavior with virtual functions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling the virtual draw() method on each shape.
• How many times: Once for each shape in the list.

How Execution Grows With Input

Each shape in the list causes one call to draw(). So if we have more shapes, we do more calls.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to draw all shapes grows in a straight line as the number of shapes increases.

Common Mistake

[X] Wrong: "Calling virtual functions inside a loop makes the program slower in a way that changes the overall time complexity."

[OK] Correct: Each virtual call takes a tiny extra step, but it still happens once per shape. So the total time still grows linearly with the number of shapes.

Interview Connect

Understanding how interface-like calls affect time helps you explain your code's performance clearly. It shows you know how design choices relate to speed.

Self-Check

"What if drawAllShapes called draw() twice for each shape? How would the time complexity change?"