Grade up

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:

1. θ(log2n)

2. θ(log2 log2n)
3. θ(n)
4. θ(n log2n)

Answer 1

i think total number of elements from root to leaf is O(logn) and if we apply binary search then we can from new leaf to root then we can find position in O(loglog(n)) time so answer should be b

Answer 2

it is may be O(n)