edited by
211 views
0 votes
0 votes

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

Is this approach correct?

For $1$ st smallest - root node is the element    -  takes $0$ comparison

For $2$ nd smallest - $2$ elements are to be compared  -  takes $1$ comparison

For $3$ rd smallest - $3$ elements are to be compared  -  takes $2$ comparison

For $4$ th smallest - $4$ elements are to be compared  -  takes $3$ comparison

.

.

For $logn^{th}$ smallest - $logn$ elements are to be compared  -  takes $logn-1$ comparison

So total comparisons would be = $1 + 2 + 3 + 4 + . . . . . . + (logn-1)$

                                                         =  $\frac{(logn)(logn+1)}{2}$

                                                         =  $O$$(logn)$$2$

Please suggest is this correct approach??

edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
monty asked Dec 29, 2016
795 views