retagged by
2,032 views
1 votes
1 votes
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 ?
retagged by

1 Answer

Best answer
4 votes
4 votes
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

Related questions

2 votes
2 votes
2 answers
1
Arjun asked Jul 3, 2016
2,977 views
Given an array of $n$ elements find the maximum continuous sum in it. For example consider the below array of $n=6$.23 4 -10 2 15 1Answer is 35.
0 votes
0 votes
0 answers
2
Arjun asked Jun 6, 2016
1,053 views
Given an arithmetic expression involving *, + only write an object oriented code for its representation and evaluation
2 votes
2 votes
1 answer
3
Arjun asked Apr 9, 2016
1,348 views
You are given a number lock of 4 digits and it accepts a serial input. What should be the minimum length of an input string so that the lock is guaranteed to open assumin...
1 votes
1 votes
0 answers
4
Arjun asked Jun 6, 2016
449 views
Write an object oriented code for representing boolean expressions and then a function for checking the equivalence of two boolean expressions.