Which of these is a true statement about the worst-case time for operations on heaps?

Both insertion and removal are better than linear
  • Insertion is better than linear, but removal is not
  • Removal is better than linear, but insertion is not
  • Neither insertion nor removal are better than linear

Insert works by putting the new element at the end of the array, and moving it up the tree as appropriate.

So its worst-case cost is proportional to the depth of the tree.

Remove works swapping the element to remove with the one at the end of the array. Then move that moved item up or down the tree, as appropriate.

So its worst-case cost is proportional to the depth of the tree.