Pure virtual functions in C++ - Time & Space Complexity

Time Complexity: Pure virtual functions

O(n)

Understanding Time Complexity

Let's explore how time complexity relates to pure virtual functions in C++.

We want to see how the program's running time changes when using pure virtual functions.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <vector>

class Shape {
public:
    virtual void draw() = 0; // pure virtual function
};

class Circle : public Shape {
public:
    void draw() override {
        // drawing circle code
    }
};

void renderShapes(std::vector<Shape*> shapes) {
    for (auto shape : shapes) {
        shape->draw();
    }
}
    

This code defines a pure virtual function draw() in a base class and calls it on a list of shapes.

Identify Repeating Operations

Look for loops or repeated calls that affect time.

• Primary operation: Calling draw() on each shape pointer.
• How many times: Once per shape in the list, so as many times as the list size.

How Execution Grows With Input

As the number of shapes grows, the number of draw() calls grows the same way.

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

Pattern observation: The work grows directly with the number of shapes.

Final Time Complexity

Time Complexity: O(n)

This means the time to run increases linearly as you add more shapes to draw.

Common Mistake

[X] Wrong: "Using pure virtual functions makes the program slower by a lot because of virtual calls."

[OK] Correct: While virtual calls add a small overhead, the main time cost comes from how many times you call the function, not the virtual call itself.

Interview Connect

Understanding how virtual functions affect time helps you explain design choices clearly and shows you know how code structure impacts performance.

Self-Check

"What if the draw() function called another loop inside it? How would that change the time complexity?"

Practice

1. What is the main purpose of a pure virtual function in C++?

easy

A. To force derived classes to implement the function

B. To allow creating objects of the base class

C. To provide a default implementation in the base class

D. To make the function private

Solution

1. Step 1: Understand pure virtual function role

   A pure virtual function is declared with = 0 and has no body in the base class.

2. Step 2: Effect on derived classes

   Derived classes must provide their own implementation of this function, or they become abstract too.

3. Final Answer:

   To force derived classes to implement the function -> Option A

4. Quick Check:

   Pure virtual function = forces implementation [OK]

Hint: Pure virtual means must override in child class [OK]

Common Mistakes:

• Thinking pure virtual allows base class objects
• Assuming pure virtual provides default code
• Confusing pure virtual with private functions

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

easy

A. void draw() = 0;

B. virtual void draw() = 0;

C. virtual void draw() {}

D. void virtual draw() = 0;

Solution

1. Step 1: Recall pure virtual function syntax

   Pure virtual functions use the keyword virtual and end with = 0;.

2. Step 2: Check each option

   virtual void draw() = 0; matches the correct syntax: virtual void draw() = 0;. Others have wrong order, missing virtual, or provide a body.

3. Final Answer:

   virtual void draw() = 0; -> Option B

4. Quick Check:

   Syntax = virtual + = 0 [OK]

Hint: Pure virtual = virtual + = 0 at end [OK]

Common Mistakes:

• Placing 'virtual' after return type incorrectly
• Adding function body {} for pure virtual
• Omitting 'virtual' keyword

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

#include <iostream>
class Shape {
public:
  virtual void draw() = 0;
};

class Circle : public Shape {
public:
  void draw() { std::cout << "Circle drawn" << std::endl; }
};

int main() {
  Circle c;
  c.draw();
  return 0;
}

medium

A. No output

B. Compilation error: cannot instantiate abstract class

C. Circle drawn

D. Runtime error

Solution

1. Step 1: Analyze class Shape

   Shape has a pure virtual function draw(), so Shape is abstract and cannot be instantiated.

2. Step 2: Analyze class Circle

   Circle overrides draw() with its own implementation, so Circle is concrete and can be instantiated.

3. Step 3: Check main function

   Circle object c is created and c.draw() prints "Circle drawn".

4. Final Answer:

   Circle drawn -> Option C

5. Quick Check:

   Derived class implements pure virtual = prints output [OK]

Hint: Derived class must implement to create objects [OK]

Common Mistakes:

• Trying to instantiate abstract base class
• Forgetting to override pure virtual function
• Expecting no output due to pure virtual

4. Identify the error in this code snippet:

class Animal {
public:
  virtual void sound() = 0;
};

class Dog : public Animal {
};

int main() {
  Dog d;
  d.sound();
  return 0;
}

medium

A. No error, code runs fine

B. Animal class should not have pure virtual functions

C. Dog object cannot be created because main is missing

D. Dog class does not implement pure virtual function sound()

Solution

1. Step 1: Check pure virtual function in Animal

   Animal declares sound() as pure virtual, so Animal is abstract.

2. Step 2: Check Dog class implementation

   Dog inherits Animal but does not implement sound(), so Dog remains abstract and cannot be instantiated.

3. Step 3: Analyze main function

   Trying to create Dog object d causes compilation error because Dog is abstract.

4. Final Answer:

   Dog class does not implement pure virtual function sound() -> Option D

5. Quick Check:

   Abstract class must implement all pure virtual functions [OK]

Hint: Derived must implement all pure virtual functions [OK]

Common Mistakes:

• Assuming base class cannot have pure virtual functions
• Thinking missing main causes error here
• Believing code runs without overriding pure virtual

5. Given the following classes, which statement is true?

#include <iostream>
class Base {
public:
  virtual void f() = 0;
  virtual void g() { std::cout << "Base g" << std::endl; }
};

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

int main() {
  Base* b = new Derived();
  b->f();
  b->g();
  delete b;
  return 0;
}

hard

A. Output is:
Derived f
Derived g

B. Output is:
Base f
Base g

C. Compilation error because Base has pure virtual function

D. Runtime error due to calling pure virtual function

Solution

1. Step 1: Understand Base class

   Base has pure virtual f() and virtual g() with implementation.

2. Step 2: Analyze Derived class

   Derived overrides both f() and g() with its own implementations.

3. Step 3: Check main function calls

   Pointer b of type Base* points to Derived object. Virtual calls invoke Derived versions of f() and g().

4. Final Answer:

   Output is: Derived f Derived g -> Option A

5. Quick Check:

   Virtual functions call derived overrides [OK]

Hint: Virtual calls use derived class methods [OK]

Common Mistakes:

• Expecting base class methods to run
• Thinking pure virtual causes compile error here
• Confusing pure virtual with runtime error