Why inheritance is used in C++ - Performance Analysis

Time Complexity: Why inheritance is used

O(n)

Understanding Time Complexity

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

Specifically, how does calling functions through inheritance change the work done as the program grows?

Scenario Under Consideration

Analyze the time complexity of this simple inheritance example.

class Animal {
public:
    virtual void speak() { }
};

class Dog : public Animal {
public:
    void speak() override { /* bark */ }
};

void makeSpeak(Animal* animals[], int n) {
    for (int i = 0; i < n; ++i) {
        animals[i]->speak();
    }
}
    

This code calls the speak function on an array of Animal pointers, which may point to different derived types.

Identify Repeating Operations

Look for repeated actions that take time.

• Primary operation: Loop through the array and call speak() on each object.
• How many times: Exactly once per element, so n times.

How Execution Grows With Input

As the number of animals grows, the number of speak calls grows the same way.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line as the number of objects increases.

Common Mistake

[X] Wrong: "Inheritance makes the program slower in a way that grows faster than the number of objects."

[OK] Correct: Each call through inheritance still happens once per object, so the total work grows linearly, not faster.

Interview Connect

Understanding how inheritance affects time helps you explain your design choices clearly and confidently.

Self-Check

"What if the speak function called another function inside a loop? How would that change the time complexity?"