in Algorithm Challenges retagged by
2,019 views
1 vote
1 vote
According to me first we sort the array in O(nlogn) time and then in O(k) time , find the product , so total time complexity is O(nlogn) , so am I right or can it be done in lesser time ?
in Algorithm Challenges retagged by
2.0k views

4 Comments

why sort? Can't we find the k largest elements and take their product if all are positive?
2
2
ya so that can be done in O(n) time right ?
0
0
Yes, but we first have to find the kth largest element.
1
1

say max element is X

k element product is Xk

So, time complexity is O(1)

Am I wrong?

0
0

1 Answer

4 votes
4 votes
Best answer
We build a max heap with the given $n$ elements. This will take $O(n)$ time to build the heap. Now every time we extract the root element and do heapify it takes $O(\log n)$ time. Since we have to extract $k^{th}$ largest element we repeat this process $k$ times. So it takes $k\log n$ time. $k$ being a constant here we can write it as $O(\log n)$ time.

Therefore total time is $O(n) + O(\log n) = O(n)$.
edited by

4 Comments

quick select algorithm can sort and select all element in O(n) time
So, it will take O(n) time
Also by heapification it will take O(n) time
0
0
@ srestha

quick select algorithm???
0
0

Related questions