-
Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is
-
- Θ (log2 n)
- Θ (log2 log2 n)
- Θ (n)
- Θ (n log2 n)
- Θ (log2 n)
Correct Option: B
Binary search takes Θ(log2 n), as the search space is continuously divided by two. In inserting in the heap we only have to move up the path from the leaf to the root, the height of a heap cannot be more than Θ(log n). So the time complexity for the insertion is Θ(log log n).
