Question

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

• A. $\Theta \left(nlo{g}_{2}n\right)$
• B. $\Theta \left(lo{g}_{2}n\right)$
• C. $\Theta \left(n\right)$
• D. $\Theta \left(lo{g}_{2}lo{g}_{2}n\right)$

Answer 1

The correct option is D $\Theta \left(lo{g}_{2}lo{g}_{2}n\right)$

After inserting an element at leaf in max heap we perform binary search on the path from the new leaf to the root to find the correct position for the newly inserted element. Comparision will take $\Theta$ (loglogn) but time will be $\Theta$ (logn) because of swap operations.