edited by
31,709 views
79 votes
79 votes

In a min-heap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time

  1. $\Theta (n \log n)$
  2. $\Theta (n)$
  3. $\Theta(\log n)$
  4. $\Theta(1)$
edited by

10 Answers

1 votes
1 votes

Sine the 7th smallest element will be from  ciel( a[7/2] to a[7]   hence only “k” comparison are required thus 0(1) is the answer

0 votes
0 votes
The question is quite ambiguous.

If the question means

i) it's a min-heap then answer would be O(1), because at worst case we need to check the roots at depth 7, and as we know asymptotic complexity tells the order of growth of time wrt 'n' or input size, here irrespective of n, if it's greater than 7 we only need to check at depth 7 at worst case as I said, even if n is 10, 100, 1000 and so on. So, it's not depending on 'n'.

ii) it's just a binary tree with the least element at the root of the tree then T would be O(nlogn) because at worst case we need to search the entire tree.
0 votes
0 votes

All the answers above are correct and very clear but if you have any confusion, and would like a programming approach,

Think of how you can write a program for it. For example, In a min heap, you know that the 3rd  smallest element would be located at left or right of the root so you can hardcode a function like

min(root->left, root->right)

Similarly you can also hardcode a function for 7th smallest element because YOU KNOW before hand that it is located among the first 7 levels and write a function that runs over some say k elements and finds a minimum.

No matter the size of N, a 1000 elements or a billion elements in that min heap, your code always takes K(constant) amount of time and doesn’t grow proportionally to N.

So answer is Θ(1)

0 votes
0 votes

Answer is option B,​​​​​​

Explanation:-

We know in binary heap the minimum element is always at the root position

Time to get minimum element is O(1).

And TC of deleting min and forming min heap again is O(logn)

Therefore, for finding 7th smallest element we have to delete element from heap 7 times.

Therefore, TC = O(7logn) = O(logn)

Answer:

Related questions

25 votes
25 votes
3 answers
4
Kathleen asked Sep 16, 2014
23,359 views
Suppose the numbers $7, 5, 1, 8, 3, 6, 0, 9, 4, 2$ are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering o...