Runtime polymorphism in C++ - Time & Space Complexity

Time Complexity: Runtime polymorphism

O(n)

Understanding Time Complexity

When using runtime polymorphism, the program decides which function to run while it is running. We want to understand how this choice affects how long the program takes.

How does the program's running time change when it picks functions at runtime?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Base {
public:
    virtual void show() { /* base action */ }
};

class Derived : public Base {
public:
    void show() override { /* derived action */ }
};

void callShow(Base* obj, int n) {
    for (int i = 0; i < n; i++) {
        obj->show();
    }
}
    

This code calls a function through a pointer to a base class. The actual function called depends on the real object type at runtime.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop calls show() method n times.
• How many times: Exactly n times, once per loop iteration.

How Execution Grows With Input

Each time we increase n, the number of calls to show() grows the same amount.

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

Pattern observation: The work grows directly with n. Doubling n doubles the calls.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Runtime polymorphism makes the code run much slower, like quadratic time."

[OK] Correct: Each call still happens once per loop. The extra step to find the right function is constant time, so total time grows linearly with n.

Interview Connect

Understanding how runtime polymorphism affects time helps you explain your code choices clearly and shows you know how programs behave in real situations.

Self-Check

"What if the show() method itself contained a loop running m times? How would the time complexity change?"