Runtime polymorphism in C++ - Time & Space Complexity

Time Complexity: Runtime polymorphism

O(n)

Understanding Time Complexity

When using runtime polymorphism, the program decides which function to run while it is running. We want to understand how this choice affects how long the program takes.

How does the program's running time change when it picks functions at runtime?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

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

This code calls a function through a pointer to a base class. The actual function called depends on the real object type at runtime.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop calls show() method n times.
• How many times: Exactly n times, once per loop iteration.

How Execution Grows With Input

Each time we increase n, the number of calls to show() grows the same amount.

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

Pattern observation: The work grows directly with n. Doubling n doubles the calls.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line as the number of calls increases.

Common Mistake

[X] Wrong: "Runtime polymorphism makes the code run much slower, like quadratic time."

[OK] Correct: Each call still happens once per loop. The extra step to find the right function is constant time, so total time grows linearly with n.

Interview Connect

Understanding how runtime polymorphism affects time helps you explain your code choices clearly and shows you know how programs behave in real situations.

Self-Check

"What if the show() method itself contained a loop running m times? How would the time complexity change?"

Practice

1. What is the main purpose of virtual functions in C++ runtime polymorphism?

easy

A. To allocate memory for objects dynamically

B. To make functions run faster by avoiding function calls

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

D. To allow derived classes to override base class methods and decide at runtime which method to call

Solution

1. Step 1: Understand virtual functions role

   Virtual functions allow a base class to declare a function that derived classes can override.

2. Step 2: Explain runtime decision

   At runtime, the program decides which overridden function to call based on the actual object type.

3. Final Answer:

   To allow derived classes to override base class methods and decide at runtime which method to call -> Option D

4. Quick Check:

   Virtual functions enable runtime method selection [OK]

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

Common Mistakes:

• Thinking virtual speeds up function calls
• Believing virtual prevents overriding
• Confusing virtual with memory allocation

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

easy

A. void display() virtual;

B. void virtual display();

C. virtual void display();

D. virtual: void display();

Solution

1. Step 1: Recall virtual function syntax

   The keyword virtual comes before the return type in the function declaration.

2. Step 2: Match correct syntax

   virtual void display(); correctly places virtual before void display();

3. Final Answer:

   virtual void display(); -> Option C

4. Quick Check:

   Virtual keyword precedes return type [OK]

Hint: Virtual always goes before return type in declaration [OK]

Common Mistakes:

• Placing virtual after function name
• Using virtual as a label or modifier incorrectly
• Missing semicolon after declaration

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

medium

A. Derived

B. Base

C. Compilation error

D. Runtime error

Solution

1. Step 1: Identify virtual function usage

   The show() function in Base is virtual and overridden in Derived.

2. Step 2: Understand pointer type and object type

   The pointer is of type Base* but points to a Derived object, so the overridden show() in Derived is called at runtime.

3. Final Answer:

   Derived -> Option A

4. Quick Check:

   Virtual function calls derived version [OK]

Hint: Virtual functions call derived method via base pointer [OK]

Common Mistakes:

• Expecting base class method output
• Confusing pointer type with object type
• Ignoring virtual keyword effect

4. Identify the error in the following code snippet related to runtime polymorphism:

class Animal {
public:
    void sound() { std::cout << "Animal sound"; }
};
class Dog : public Animal {
public:
    void sound() { std::cout << "Bark"; }
};
int main() {
    Animal* a = new Dog();
    a->sound();
    delete a;
    return 0;
}

medium

A. Incorrect pointer type declaration

B. Missing virtual keyword in base class function

C. Derived class function should be static

D. Memory leak due to missing delete

Solution

1. Step 1: Check base class function declaration

   The base class function sound() is not declared virtual, so no runtime polymorphism occurs.

2. Step 2: Effect on function call

   Because sound() is not virtual, calling a->sound() calls the base class version, not the derived one.

3. Final Answer:

   Missing virtual keyword in base class function -> Option B

4. Quick Check:

   Virtual needed for runtime polymorphism [OK]

Hint: Base function must be virtual for polymorphism [OK]

Common Mistakes:

• Assuming override works without virtual
• Thinking pointer type causes error
• Ignoring virtual keyword importance

5. Given the classes below, what will be the output when ptr->identify() is called?

class Shape {
public:
    virtual void identify() { std::cout << "Shape"; }
};
class Circle : public Shape {
public:
    void identify() override { std::cout << "Circle"; }
};
class ColoredCircle : public Circle {
public:
    void identify() override { std::cout << "Colored Circle"; }
};
int main() {
    Shape* ptr = new ColoredCircle();
    ptr->identify();
    delete ptr;
    return 0;
}

hard

A. Colored Circle

B. Circle

C. Shape

D. Compilation error due to multiple overrides

Solution

1. Step 1: Trace virtual function overrides

   identify() is virtual in Shape, overridden in Circle, and again in ColoredCircle.

2. Step 2: Determine actual object type at runtime

   The pointer ptr is of type Shape* but points to a ColoredCircle object, so the most derived override runs.

3. Final Answer:

   Colored Circle -> Option A

4. Quick Check:

   Most derived override called at runtime [OK]

Hint: Runtime calls most derived override in inheritance chain [OK]

Common Mistakes:

• Expecting base or intermediate class output
• Thinking multiple overrides cause errors
• Ignoring virtual override chain