Function overriding in C++ - Time & Space Complexity

Time Complexity: Function overriding

O(n)

Understanding Time Complexity

When we use function overriding, we replace a parent class function with a child class version. We want to see how this affects the time it takes to run the program.

How does calling an overridden function change the work done as input grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Base {
public:
    int n;
    virtual void display() {
        for(int i = 0; i < n; i++) {
            // some work
        }
    }
};

class Derived : public Base {
public:
    void display() override {
        for(int i = 0; i < n; i++) {
            // some different work
        }
    }
};

void callDisplay(Base* obj) {
    obj->display();
}
    

This code shows a base class and a derived class both having a display function that loops n times. The callDisplay function calls display through a base pointer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for loop inside the display function that runs n times.
• How many times: Exactly n times per call to display.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	About 10 loop steps
100	About 100 loop steps
1000	About 1000 loop steps

Pattern observation: The work grows directly with n. If n doubles, the work doubles too.

Final Time Complexity

Time Complexity: O(n)

This means the time to run display grows in a straight line with the input size n.

Common Mistake

[X] Wrong: "Overriding a function makes the program slower or faster automatically."

[OK] Correct: Overriding only changes which code runs, not how many times the main loop runs. The time depends on the loop inside, not the override itself.

Interview Connect

Understanding how overriding affects time helps you explain code behavior clearly. It shows you know when the program work changes and when it stays the same.

Self-Check

"What if the derived class display function had two nested loops each running n times? How would the time complexity change?"