Pure virtual functions in C++ - Time & Space Complexity

Time Complexity: Pure virtual functions

O(n)

Understanding Time Complexity

Let's explore how time complexity relates to pure virtual functions in C++.

We want to see how the program's running time changes when using pure virtual functions.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <vector>

class Shape {
public:
    virtual void draw() = 0; // pure virtual function
};

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

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

This code defines a pure virtual function draw() in a base class and calls it on a list of shapes.

Identify Repeating Operations

Look for loops or repeated calls that affect time.

• Primary operation: Calling draw() on each shape pointer.
• How many times: Once per shape in the list, so as many times as the list size.

How Execution Grows With Input

As the number of shapes grows, the number of draw() calls grows the same way.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run increases linearly as you add more shapes to draw.

Common Mistake

[X] Wrong: "Using pure virtual functions makes the program slower by a lot because of virtual calls."

[OK] Correct: While virtual calls add a small overhead, the main time cost comes from how many times you call the function, not the virtual call itself.

Interview Connect

Understanding how virtual functions affect time helps you explain design choices clearly and shows you know how code structure impacts performance.

Self-Check

"What if the draw() function called another loop inside it? How would that change the time complexity?"