Virtual functions in C++ - Time & Space Complexity

Time Complexity: Virtual functions

O(n)

Understanding Time Complexity

When using virtual functions in C++, the program decides at runtime which function to call. This adds a small extra step compared to normal function calls.

We want to understand how this extra step affects the program's running time as the input grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

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

This code calls a virtual function show() on each object in an array of pointers.

Identify Repeating Operations

• Primary operation: Calling the virtual function show() on each object.
• How many times: Exactly n times, once per element in the array.

How Execution Grows With Input

Each call to show() requires a small extra step to find the right function version, but this step happens once per element.

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

Pattern observation: The total work grows directly with the number of elements, so doubling the input doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the number of objects we call the virtual function on.

Common Mistake

[X] Wrong: "Virtual functions make the program run much slower, so the time complexity becomes worse than linear."

[OK] Correct: Each virtual call adds a tiny fixed cost, but it still happens once per element. The overall time still grows linearly with input size.

Interview Connect

Understanding how virtual functions affect time helps you explain performance trade-offs clearly. This skill shows you know how features impact program speed in real situations.

Self-Check

"What if the virtual function called inside the loop itself contained a loop over the input size? How would the time complexity change?"