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

Practice

1. What is the main purpose of declaring a function as virtual in a C++ base class?

easy

A. To allow derived classes to override the function and enable runtime polymorphism

B. To make the function inline for faster execution

C. To prevent the function from being overridden in derived classes

D. To make the function static and shared among all objects

Solution

1. Step 1: Understand virtual function role

   A virtual function in a base class allows derived classes to provide their own implementation that will be called at runtime.

2. Step 2: Recognize runtime polymorphism

   This mechanism enables dynamic dispatch, meaning the program decides which function to call based on the actual object type, not the pointer type.

3. Final Answer:

   To allow derived classes to override the function and enable runtime polymorphism -> Option A

4. Quick Check:

   Virtual function = runtime polymorphism [OK]

Hint: Virtual means choose function at runtime, not compile time [OK]

Common Mistakes:

• Confusing virtual with inline functions
• Thinking virtual prevents overriding
• Assuming virtual makes function static

2. Which of the following is the correct syntax to declare a virtual function named display in a base class?

easy

A. virtual void display();

B. void virtual display();

C. virtual display void();

D. void display() virtual;

Solution

1. Step 1: Recall correct virtual function syntax

   The keyword virtual must come before the return type and function name.

2. Step 2: Check each option

   virtual void display(); correctly places virtual before void display();. Others have incorrect order or placement.

3. Final Answer:

   virtual void display(); -> Option A

4. Quick Check:

   virtual before return type = correct syntax [OK]

Hint: Put 'virtual' before return type in function declaration [OK]

Common Mistakes:

• Placing virtual after function name
• Mixing order of keywords
• Adding virtual at the end of declaration

3. Consider 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* ptr = new Derived();
    ptr->show();
    delete ptr;
    return 0;
}

What is the output when this program runs?

medium

A. Base

B. Runtime error

C. Derived

D. Compilation error

Solution

1. Step 1: Analyze pointer and object types

   The pointer is of type Base* but points to a Derived object.

2. Step 2: Understand virtual function call

   Because show() is virtual, the Derived version is called at runtime, printing "Derived".

3. Final Answer:

   Derived -> Option C

4. Quick Check:

   Virtual function calls derived version [OK]

Hint: Virtual calls use actual object type, not pointer type [OK]

Common Mistakes:

• Assuming base class function runs
• Confusing override keyword effect
• Expecting compilation or runtime errors

4. Identify the error in the following code snippet:

class Base {
public:
    void display() { std::cout << "Base"; }
};
class Derived : public Base {
public:
    void display() override { std::cout << "Derived"; }
};

medium

A. Derived class function cannot have the same name as base class function

B. No error, code is correct

C. Override keyword is not allowed in derived class

D. Base class function must be declared virtual to allow override

Solution

1. Step 1: Check base class function declaration

   The base class function display() is not declared virtual.

2. Step 2: Understand override keyword usage

   The override keyword requires the base function to be virtual; otherwise, it causes a compilation error.

3. Final Answer:

   Base class function must be declared virtual to allow override -> Option D

4. Quick Check:

   Override needs virtual base function [OK]

Hint: Base function must be virtual to use override in derived [OK]

Common Mistakes:

• Ignoring missing virtual in base
• Thinking override is optional
• Assuming same name always means override

5. Given the classes below, what will be the output of the program?

class Animal {
public:
    virtual void sound() { std::cout << "Animal sound "; }
};
class Dog : public Animal {
public:
    void sound() override { std::cout << "Bark "; }
};
class Cat : public Animal {
public:
    void sound() override { std::cout << "Meow "; }
};

int main() {
    Animal* animals[3];
    animals[0] = new Animal();
    animals[1] = new Dog();
    animals[2] = new Cat();

    for (int i = 0; i < 3; i++) {
        animals[i]->sound();
    }

    for (int i = 0; i < 3; i++) {
        delete animals[i];
    }
    return 0;
}

hard

A. Animal sound Animal sound Animal sound

B. Animal sound Bark Meow

C. Bark Meow Animal sound

D. Compilation error due to array of pointers

Solution

1. Step 1: Analyze array of Animal pointers

   The array holds pointers to objects of types Animal, Dog, and Cat respectively.

2. Step 2: Understand virtual function calls in loop

   Calling sound() on each pointer calls the overridden version based on actual object type, printing "Animal sound ", "Bark ", and "Meow ".

3. Final Answer:

   Animal sound Bark Meow -> Option B

4. Quick Check:

   Virtual calls print actual object sounds [OK]

Hint: Virtual functions call derived versions in arrays of base pointers [OK]

Common Mistakes:

• Expecting base class sound for all
• Confusing array pointer syntax
• Assuming compilation error with polymorphism