1

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

a) Θ(nlogn)
b) Θ(n)
c) Θ(logn)
d) Θ(1)

==========================================================================

I am so confused between option c and d. Do we need to do Extract Min 7 times or simply do comparisons as at root level - 0 comparison, at 1st level - 3 comparison between root and LC and RC and so on.

Gassa
  • 8,546
  • 3
  • 29
  • 49
Geeklovenerds
  • 327
  • 6
  • 21

4 Answers4

4

I'd say the question is ambiguous.

If we have to use the heap interface, we can do no better than extract the minimum 6 times, and look at the 7-th minimum. Each time except the last, we can spend anywhere from 1 (best case) to log n (worst case) operations, so it's O(log n) but not Theta of anything. The 7-th operation is Theta(1).

If we can exploit the heap's internal structure, as Yves Daoust already pointed out, we can be sure that the heap contains its minimum element in its first 7 levels, which have at most 1+2+4+8+16+32+64=127 elements. Finding a minimum in the first 127 numbers of the array where the heap is stored is Theta(1) because, however large, 127 is still a constant and does not depend on n.

Seeing that option (c) is not really a correct answer in first case (It would be if O() was used instead of Theta()), I'd go with (d).

Gassa
  • 8,546
  • 3
  • 29
  • 49
  • 1
    Interesting remark about the restriction to the heap interface. –  Jun 20 '18 at 08:15
  • @YvesDaoust What I say is `Theta()` does not make sense for the first part, only `O()` does. In the best case (sift-down exits after first iteration), extracting a minimum takes `1` operation. In the worst case (sift-down goes all the way to the bottom), it takes `log n` operations. So sift-down does not belong to any `Theta()` complexity class. The tight bound in `O()` is `O(log n)`. I understand that `O(log n)` is a subset of `O(n)` etc., but the same does not hold for `Theta()`. Right?.. – Gassa Jun 20 '18 at 08:16
  • 1
    The question is not explicit enough about that. You are right to say that there is no Θ class for the raw running time in the case of heap operations. But the *worst-case* running time is indeed Θ(Log n). [The raw running time is not a unequivocal function of n. The worst-case, best-case and average-case are.] When we limit ourselves to the first 7 levels, we of course have O(1)=Θ(1). –  Jun 20 '18 at 08:23
  • 1
    @YvesDaoust Hmm, I see, thanks! So option `(c)` would be a correct answer if the question was about worst-case performance, and it mentioned we have to stick to the interface. That looks like too much unmentioned defaults to me, so I'd stick with `(d)`. – Gassa Jun 20 '18 at 08:28
  • @Gassa May be please explain this line in a simplified manner - because, however large, 127 is still a constant and does not depend on "n" – Geeklovenerds Jun 20 '18 at 10:35
  • @MicroLegions Whether `n = 1` or `n = 1000` or `n = 10^{10^{10}}`, 127 remains just the constant 127, it does not depend on `n`. We are asked to find the complexity in terms of `n`. The complexity classes drop the constant, so `O (127 * n^0) = O (n^0) = O (1)`. – Gassa Jun 20 '18 at 14:16
  • @gassa I'm so so sorry to bother, but why you took n^0 in O (127 * n^0). Can I say as n = 100 and O(127*100) = O(12700) which is nothing but a constant? – Geeklovenerds Jun 21 '18 at 06:59
  • @MicroLegions That's how asymptotic notation works. The phrase "time is O(n^3)" means "there exists a constant C such that, as n tends to infinity, the time has an upper bound of C * n^3". So, the variable n is already bounded as "the thing which tends to infinity", it is incorrect to simultaneously declare it a constant. The "7th smallest element", on the other hand, is given as a constant in the problem statement. If the problem asked what would happen when we need the k-th smallest element, the 127 would turn into 2^k - 1. – Gassa Jun 21 '18 at 08:49
  • @Gassa if the question is finding the K'th smallest element in min heap of n nodes? Then can we also say it's O(k) or O(1) as K is a constant? – Geeklovenerds Aug 06 '19 at 16:26
  • @Geeklovenerds The explanation presented an O(2^k) way to do it. If k is a constant, yeah, we can say it's O(1). How meaningful it is in practice? Depends on the particular case. – Gassa Aug 06 '19 at 21:15
3

In the worst of the situations, the 7th element will be found in the 7 first levels of the heap, which contain at most 127 elements. You can find it by sorting these elements, which takes O(1).

CAUTION: this is not meant to be an efficient procedure, it is a simple theoretical argument to prove that the problem can be solved in constant time.

A possibly better procedure is to perform the selection phase of heapsort on the 127 elements heap, which will take at worse like lg 127 + lg 126 + lg 125 + lg 124 + lg 123 + lg 122 + lg 121 operations (very gross estimate, but it doesn't matter, it is O(1)).

2

In min heap elements are not stored like binary search tree (i.e. smaller than root on left side and larger on right). A smaller element can present at any children node therefore, we cannot search element like we do in binary search tree.

So, we need to first pop top 6 elements from heap and store them in array, now 7th element is on root so we pop it and store it. Now we push all 6 element that we pop earlier into heap.

Time Complexity:- 7 operation to pop and 6 operation to push therefore total 7 + 6 = 13 operation. And each operation cost logn amount of time. So, time complexity becomes 13*logn or simply O(logn)

Kapil Deshpande
  • 39
  • 5
  • Can we apply Heapsort? If not, why? – Geeklovenerds Jun 20 '18 at 07:08
  • yes you can but it is very inefficient its time complexity is O(nlogn) while the current algorithm's time complexity is O(logn) – Kapil Deshpande Jun 20 '18 at 07:46
  • 1
    No, you have to search among a bounded number of elements, hence O(1), even with sorting. –  Jun 20 '18 at 08:02
  • After popping each element, you will have to run the heapify function to regenerate a min-heap which would amount to O(logn) time complexity. So popping is the wrong approach here. Instead if you limit the search area to top 7 levels then finding the 7th smallest element is O(1). – anantdark Jun 22 '22 at 02:58
  • https://gateoverflow.in/1110/Gate-cse-2003-question-23 – anantdark Jun 22 '22 at 03:00
0

The answer will be O(n).Everyone here is assuming that you will have a Constant range under which you can find the answer so O(1) will be the answer but they miss a point that a min heap can have duplicates . Lets say that 6th smallest element has 1 million duplicates then how would you calculate the range when it is not even given the number of duplicates is and on top of that let say the last element is 7th smallest you will have to search the whole array. Hence the answer is n.

Batman
  • 47
  • 1
  • 6