CODEWITHSUNDEEP
algorithmdata-structurestime-complexityheap
GameYoker
GameYoker

Reputation: 55

Find log n greatest entries in O(n) time

Is there a way to find the log n greatest elements in an array with n elements in O(n) time?

I would create an array based HeapPriorityQueue, because if all elements are available the heap can be created in O(n) time using bottom up heap construction. Then removing the first element of this priorityqueue should be in O(1) time isn`t?

Upvotes: 2

Views: 194

Answers (2)

Heladio Amaya
Heladio Amaya

Reputation: 968

Basically, yes. The creation of the heap takes O(n) and this dominates the algorithm.

Removing the first element may take either O(1) if the heap does not updates it's keys after removing or O(log n) if it does. Either way the complexity of removing log(n) elements from the heap with and without updating would be O(log n * log n) and O(log n) respectively. Both of which are sublinear.

Upvotes: 1

amit
amit

Reputation: 178521

Then removing the first element of this priority queue should be in O(1) time isn`t?

That will be O(logn), since you also remove the first element. Looking at it without removing is O(1). Repeating this removal logn times will be O(log^2(n)), which is still in O(n), so this solution will indeed meet the requirements.

Another option is to use selection algorithm to find the log(n)'th biggest element directly, which will be O(n) as well.

Upvotes: 4

Related Questions