Practice question · True or false
Because an ADT's interface says nothing about cost, two correct implementations of the same interface can differ enormously in performance.
Hints
- The interface names operations; it does not price them.
- A list and a hash table can both offer
contains.
Show the answer
True
Why
True. contains is O(n) on a list and O(1) on a hash table, and both satisfy the same interface. That is the point and the danger of an ADT: it lets you swap implementations freely, and it lets you swap in one whose costs make every caller quadratic without changing a line of them.
Practise Abstract Data Use
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Abstract Data Use
- A stack ADT implemented with a fixed-size array can overflow when pushed too many times; the same ADT over a…
- A team replaces a stack's array implementation with a linked-node one. The published operations behave…
- A library documents a function's behaviour but not its complexity. Callers then write loops assuming it is…
- Order what happens when an object is created and then used.
- A stack ADT is being documented. Sort each statement by whether it belongs in the published interface or is…