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?"

Practice

1. What is function overriding in C++?

easy

A. A child class provides its own version of a parent class's virtual function.

B. A function with the same name but different parameters in the same class.

C. A function that is called automatically when an object is created.

D. A function that cannot be changed once defined.

Solution

1. Step 1: Understand function overriding concept

   Function overriding means a child class changes the behavior of a function defined in its parent class.

2. Step 2: Identify correct description

   A child class provides its own version of a parent class's virtual function. correctly describes overriding as providing a new version of a parent's virtual function in the child class.

3. Final Answer:

   A child class provides its own version of a parent class's virtual function. -> Option A

4. Quick Check:

   Function overriding = child changes parent's virtual function [OK]

Hint: Overriding means child changes parent's virtual function [OK]

Common Mistakes:

• Confusing overriding with overloading
• Thinking overriding happens without virtual keyword
• Believing overriding applies to non-virtual functions

2. Which of the following is the correct syntax to override a function in C++11 and later?

easy

A. void func() virtual override;

B. override void func();

C. void func() override;

D. virtual void func() override;

Solution

1. Step 1: Recall override syntax in child class

   In C++11+, the child class function uses the same signature and adds the 'override' keyword after the function declaration.

2. Step 2: Identify correct syntax

   virtual void func() override; shows the correct syntax: 'virtual void func() override;'. The 'virtual' keyword can be used in the child class but is optional; however, it is valid and common to include it.

3. Final Answer:

   virtual void func() override; -> Option D

4. Quick Check:

   Child function uses virtual and override keywords correctly [OK]

Hint: Use 'override' after function signature in child class; 'virtual' is optional but allowed [OK]

Common Mistakes:

• Adding 'virtual' keyword after function name
• Placing 'override' before function name
• Omitting 'override' keyword entirely

3. What will be the output of the following code?

class Base {
public:
    virtual void show() { std::cout << "Base"; }
};
class Derived : public Base {
public:
    void show() override { std::cout << "Derived"; }
};
int main() {
    Base* b = new Derived();
    b->show();
    delete b;
    return 0;
}

medium

A. Derived

B. Base

C. Compilation error

D. Runtime error

Solution

1. Step 1: Understand virtual function behavior

   The pointer 'b' is of type Base* but points to a Derived object. Because 'show' is virtual, the Derived version is called.

2. Step 2: Trace the function call

   Calling b->show() invokes Derived::show(), printing "Derived".

3. Final Answer:

   Derived -> Option A

4. Quick Check:

   Virtual function calls child's version [OK]

Hint: Virtual functions call child's version via base pointer [OK]

Common Mistakes:

• Expecting base class output
• Forgetting to make base function virtual
• Confusing pointer type with object type

4. Identify the error in the following code snippet:

class Parent {
public:
    void display() { std::cout << "Parent"; }
};
class Child : public Parent {
public:
    void display() override { std::cout << "Child"; }
};

medium

A. Child's display() should not use override keyword.

B. Parent's display() must be declared virtual to override.

C. display() must return int, not void.

D. No error, code is correct.

Solution

1. Step 1: Check virtual keyword in parent

   For overriding to work, the base class function must be declared virtual.

2. Step 2: Analyze override keyword usage

   Child uses 'override' but Parent's display() is not virtual, causing a compilation error.

3. Final Answer:

   Parent's display() must be declared virtual to override. -> Option B

4. Quick Check:

   Base function must be virtual for override [OK]

Hint: Base function must be virtual to allow override [OK]

Common Mistakes:

• Ignoring virtual keyword in base class
• Thinking override works without virtual
• Assuming override keyword is optional

5. Given the classes below, what will be the output of obj->print();?

class A {
public:
    virtual void print() { std::cout << "A"; }
};
class B : public A {
public:
    void print() override { std::cout << "B"; }
};
class C : public B {
public:
    void print() override { std::cout << "C"; }
};

int main() {
    A* obj = new C();
    obj->print();
    delete obj;
    return 0;
}

hard

A. A

B. B

C. C

D. Compilation error

Solution

1. Step 1: Understand pointer and object types

   Pointer 'obj' is of type A*, but it points to an object of class C.

2. Step 2: Follow virtual function overriding chain

   Since print() is virtual and overridden in B and C, the most derived override (C::print) is called.

3. Final Answer:

   C -> Option C

4. Quick Check:

   Virtual call resolves to most derived override [OK]

Hint: Virtual calls use most derived override at runtime [OK]

Common Mistakes:

• Expecting base class output
• Confusing pointer type with object type
• Ignoring virtual function behavior