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