Time complexity to invoke virtual functions in C++

Question

Assume an inheritance hierarchy with type Base that has F virtual functions, D different derived types, and assuming that each derived type overrides all of the virtual functions.

What is the time complexity to invoke one of the virtual functions for a pointer p of type Base*?

Also, What is the space complexity of the system if there are O objects total (equally divided among the types) and all objects have the same data members?

Answer 1

The time complexity to invoke a function is O(1). Each class has a 'vtable', which is essentially a struct of function pointers - each object has a pointer to this vtable, so calling a virtual function is just looking up the function pointer in the vtable and calling it.

The space completity of O objects is O(O), since it's linear in the number of objects.

Answer 2

Object size is calculated as a total sum of attributes size of that object + size of pointer to a virtual table

so if

class Base {
    int a;
    char b;
    virtual void f();
    virtual void g();
};

that means size of Base b is sizeof(int) + sizeof(b) + sizeof a vtable ptr.

If you say all objects (derived and not derived) have the same members their size is the same.

Answer 3

There is a one pointer to a virtual table, which contains all the virtual functions, so accessing it and dereferencing a function is O(1).

The space complexity is O(F) (or O(1) if F is the constant)since there is one address table for all the objects of the same class.

A quote from Wikipedia: An object's dispatch table will contain the addresses of the object's dynamically bound methods. Method calls are performed by fetching the method's address from the object's dispatch table. The dispatch table is the same for all objects belonging to the same class, and is therefore typically shared between them. Objects belonging to type-compatible classes (for example siblings in an inheritance hierarchy) will have dispatch tables with the same layout: the address of a given method will appear at the same offset for all type-compatible classes. Thus, fetching the method's address from a given dispatch table offset will get the method corresponding to the object's actual class.