Base class pointers in C++ - Time & Space Complexity

Time Complexity: Base class pointers

O(n)

Understanding Time Complexity

Let's explore how the time it takes to run code changes when using base class pointers in C++.

We want to know how the program's steps grow as the input size changes when accessing objects through base class pointers.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Base {
public:
    virtual void display() {}
};

class Derived : public Base {
public:
    void display() override {}
};

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

This code calls a virtual function on each object pointed to by base class pointers in an array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

Each additional element adds one more function call through the base pointer.

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

Pattern observation: The number of calls grows directly with the number of elements.

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: "Using base class pointers makes the function calls slower in a way that changes the overall time complexity."

[OK] Correct: Each call still happens once per element, so the total steps grow linearly. Virtual calls add a small fixed cost but do not change the growth pattern.

Interview Connect

Understanding how loops and virtual function calls scale helps you explain performance clearly and confidently in real coding situations.

Self-Check

What if we replaced the loop with nested loops calling display() on pairs of objects? How would the time complexity change?