Interface-like behavior in C++ - Time & Space Complexity

Time Complexity: Interface-like behavior

O(n)

Understanding Time Complexity

When we use interface-like behavior in C++, we often call functions through pointers or references to base classes. This can affect how long the program takes to run.

We want to know how the time to run changes when we call methods this way.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Shape {
public:
    virtual void draw() {}
};

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

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

This code calls the draw method on each shape using interface-like behavior with virtual functions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling the virtual draw() method on each shape.
• How many times: Once for each shape in the list.

How Execution Grows With Input

Each shape in the list causes one call to draw(). So if we have more shapes, we do more calls.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to draw all shapes grows in a straight line as the number of shapes increases.

Common Mistake

[X] Wrong: "Calling virtual functions inside a loop makes the program slower in a way that changes the overall time complexity."

[OK] Correct: Each virtual call takes a tiny extra step, but it still happens once per shape. So the total time still grows linearly with the number of shapes.

Interview Connect

Understanding how interface-like calls affect time helps you explain your code's performance clearly. It shows you know how design choices relate to speed.

Self-Check

"What if drawAllShapes called draw() twice for each shape? How would the time complexity change?"

Practice

1. What is the main purpose of an interface-like class in C++?

easy

A. To store data members for derived classes

B. To provide full function implementations for reuse

C. To define functions that derived classes must implement

D. To create objects directly without inheritance

Solution

1. Step 1: Understand interface concept

   Interfaces specify what functions a class must have but do not provide their code.

2. Step 2: Identify interface role in C++

   In C++, interfaces are created using pure virtual functions that derived classes must implement.

3. Final Answer:

   To define functions that derived classes must implement -> Option C

4. Quick Check:

   Interface = function declarations only [OK]

Hint: Interfaces declare required functions without code [OK]

Common Mistakes:

• Thinking interfaces provide function code
• Assuming interfaces hold data members
• Believing interfaces can be instantiated

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

easy

A. virtual void func() = 0;

B. virtual void func();

C. void func() override;

D. virtual void func() = 1;

Solution

1. Step 1: Recall pure virtual function syntax

   Pure virtual functions are declared with '= 0' after the function signature.

2. Step 2: Check options for correct syntax

   virtual void func() = 0; uses '= 0' correctly, others do not match pure virtual syntax.

3. Final Answer:

   virtual void func() = 0; -> Option A

4. Quick Check:

   Pure virtual = '= 0' [OK]

Hint: Pure virtual functions end with '= 0;' [OK]

Common Mistakes:

• Using '= 1' instead of '= 0'
• Omitting 'virtual' keyword
• Confusing override with pure virtual

3. Consider the following code:

class IShape {
public:
    virtual double area() const = 0;
};

class Circle : public IShape {
    double radius;
public:
    Circle(double r) : radius(r) {}
    double area() const override { return 3.14 * radius * radius; }
};

int main() {
    Circle c(2);
    std::cout << c.area();
    return 0;
}

What is the output of this program?

medium

A. 4

B. Compilation error

C. 3.14

D. 12.56

Solution

1. Step 1: Calculate area of circle with radius 2

   Area = π * r² = 3.14 * 2 * 2 = 12.56

2. Step 2: Confirm code compiles and runs correctly

   Circle implements pure virtual function area(), so no error; output is area value.

3. Final Answer:

   12.56 -> Option D

4. Quick Check:

   Area = 3.14 * 4 = 12.56 [OK]

Hint: Calculate area formula carefully [OK]

Common Mistakes:

• Forgetting to implement pure virtual function
• Using wrong radius value
• Expecting compilation error

4. What is wrong with this code snippet?

class IAnimal {
public:
    virtual void speak() = 0;
};

class Dog : public IAnimal {
public:
    void speak() { std::cout << "Woof"; }
};

int main() {
    IAnimal a;
    a.speak();
    return 0;
}

medium

A. Missing override keyword in Dog::speak()

B. Cannot create object of abstract class IAnimal

C. speak() should return a value

D. Dog class must be abstract

Solution

1. Step 1: Identify abstract class usage

   IAnimal has a pure virtual function, so it is abstract and cannot be instantiated.

2. Step 2: Check main() for object creation

   Code tries to create IAnimal a; which is illegal and causes compilation error.

3. Final Answer:

   Cannot create object of abstract class IAnimal -> Option B

4. Quick Check:

   Abstract class objects cannot be created [OK]

Hint: Abstract classes cannot be instantiated [OK]

Common Mistakes:

• Ignoring abstract class instantiation rules
• Thinking override keyword is mandatory
• Assuming pure virtual functions must return values

5. You want to create an interface-like class IPrinter with a pure virtual function print(). Then create two classes ConsolePrinter and FilePrinter that implement print(). Which of the following code snippets correctly demonstrates this?

hard

A. class IPrinter {
public:
virtual void print() = 0;
};

class ConsolePrinter : public IPrinter {
public:
void print() override { std::cout << "Console output"; }
};

class FilePrinter : public IPrinter {
public:
void print() override { /* write to file */ }
};

B. class IPrinter {
public:
void print() { }
};

class ConsolePrinter : public IPrinter {
public:
void print() { std::cout << "Console output"; }
};

C. class IPrinter {
public:
virtual void print();
};

class ConsolePrinter : public IPrinter {
};

D. class IPrinter {
public:
virtual void print() = 1;
};

Solution

1. Step 1: Define interface with pure virtual function

   IPrinter declares print() as pure virtual with '= 0', making it an interface.

2. Step 2: Implement print() in derived classes

   ConsolePrinter and FilePrinter override print() with their own code, fulfilling interface contract.

3. Final Answer:

   Code snippet D correctly defines interface and implementations -> Option A

4. Quick Check:

   Pure virtual = 0 + override implementations [OK]

Hint: Use '= 0' for pure virtual and override in derived [OK]

Common Mistakes:

• Using '= 1' instead of '= 0' for pure virtual
• Not implementing pure virtual functions in derived classes
• Defining interface functions with bodies