Why polymorphism is needed in C++ - Performance Analysis

Time Complexity: Why polymorphism is needed

O(n)

Understanding Time Complexity

We want to understand how using polymorphism affects the time it takes for a program to run.

Specifically, does choosing polymorphism change how the program's work grows as input grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

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

This code calls the draw function on many shapes using polymorphism to decide which draw runs.

Identify Repeating Operations

• Primary operation: Loop over all shapes calling draw()
• How many times: Once per shape in the list

How Execution Grows With Input

Each shape in the list causes one draw call, so work grows as the number of shapes grows.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line as you add more shapes.

Common Mistake

[X] Wrong: "Polymorphism makes the program slower in a way that changes how time grows with input size."

[OK] Correct: Polymorphism adds a small fixed cost per call but does not change the overall growth pattern, which depends on how many shapes you have.

Interview Connect

Understanding how polymorphism affects time helps you explain design choices clearly and shows you know how code structure relates to performance.

Self-Check

"What if we replaced the loop with recursion calling draw on each shape? How would the time complexity change?"