Register

GATEBOOK exam

320 views

1 Answer

2 votes
2 votes
Ans Option A $\large \Theta (n)$

Bcz we need to check elements  in array sequentially upto last level -1 of min heap for min heap property .

Which contains asymptotically (n/2) elements so

i.e . array representation of min heap

4,6,10,7,9,15,11. Size= 7

We have to check heap property upto last level-1 so aymptotically $\large   \Theta (n/2) $ is equals to $ \large \Theta (n) $

$ \large \Theta (n) $ is ans.
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

11.1k
views
1 answers
1 votes
Pranabesh Ghosh 1 asked Aug 30, 2016
11,078 views
GATEBOOK exam
Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array ... be selection sort.D) The algorithm is neither selection sort nor insertion sort.
User Avatar
606
views
2 answers
0 votes
Pranabesh Ghosh 1 asked Aug 30, 2016
606 views
GATEBOOK exam
Given an array of integers what is the worst case time complexity that would find pair of integers which are same?A) O(nlogn)B) O(n)C) O()D) O(nloglogn)
User Avatar
747
views
1 answers
4 votes
Pranabesh Ghosh 1 asked Aug 30, 2016
747 views
GATEBOOK exam
A min heap with 1000 elements is stored in an array. What is the maximum possible index number for 9th min element?A) 254B) 100C) 9D) 511
User Avatar
822
views
1 answers
2 votes
Pranabesh Ghosh 1 asked Aug 30, 2016
822 views
GATEBOOK exam
Suppose that an application have a huge number of insert operations, but only few delete max operations. Which priority-queue implementation would be most effective:A) Max heapB) unordered arrayC) ordered arrayD) Binary search tree
User Avatar
Link Copied!