Question

Consider a binary heap (min heap) with N elements in it. What is the worst-case time complexity of the "ADD" operation?

a. O(1)
b. O(log N)
c. O(N)
d. O(N²)

Answer 1

The worst-case time complexity of the 'ADD' operation in a binary heap (min heap) with N elements is O(log N).

Step-by-step explanation:

The worst-case time complexity of the 'ADD' operation in a binary heap (min heap) with N elements is O(log N).

When a new element is added to the min heap, it is inserted at the bottom of the heap and then 'bubbled up' by comparing it with its parent until the heap property is satisfied.

This process of 'bubbling up' the new element takes O(log N) time because the height of the heap is log(N). Therefore, the worst-case time complexity of the 'ADD' operation in a binary heap is O(log N).