CameraIcon
CameraIcon
SearchIcon
MyQuestionIcon
MyQuestionIcon
1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
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
Θ(nlog2n)
No worries! We‘ve got your back. Try BYJU‘S free classes today!
B
Θ(log2n)
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
Θ(n)
No worries! We‘ve got your back. Try BYJU‘S free classes today!
D
Θ(log2log2n)
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
Open in App
Solution

The correct option is D Θ(log2log2n)
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 Θ (loglogn) but time will be Θ (logn) because of swap operations.

flag
Suggest Corrections
thumbs-up
0
Join BYJU'S Learning Program
similar_icon
Related Videos
thumbnail
lock
Fundamental Laws of Logarithms
MATHEMATICS
Watch in App
Join BYJU'S Learning Program
CrossIcon