The Gateway to Computer Science Excellence
+1 vote
566 views
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 by Loyal (6.3k points) | 566 views
+2
why sort? Can't we find the k largest elements and take their product if all are positive?
0
ya so that can be done in O(n) time right ?
+1
Yes, but we first have to find the kth largest element.
0

say max element is X

k element product is Xk

So, time complexity is O(1)

Am I wrong?

1 Answer

+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 kth largest element we repeat this process k times . So it takes klogn 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).
by Loyal (7.4k points)
selected by
+2
$k$ is also an input. Procedure is correct but can be optimized using the algorithm for finding kth largest element in $O(n)$.
+1
Sir are you talking about quick sort ?
+2
Default quick sort won't do this in linear time - but a variant of it can do.
0
need quick sort because then no need to heapify again and again. right?
0
@arjun sir, I think she has given the perfect answer. If the K is also an input then also it will take only $k.log n$ time (maximum will be $n.log n$ time), which is definitely less than quicksort $k.n$ times (maximum will be $n^2$ times. .

And actually this is a very famous interview problem, and she has stated the perfect solution. Which is suggested by some of the best profs.

And you have suggested the Kth largest number algorithm, It perform real bad if K is very less. And its theoretically seems that perform better than heap method but its not a huge improvement. Its similar to strassen Matrix multiplication over general algorithm, covert 8 multiplication and 4 addition into 7 multiplication and 17 addition and shows some 0.19 improvement..
0
@Arjun sir But here is the biggest question, Can you really modify the Kth order selection algorithm for this task.? I do not think so or it will not be that efficient then.
0

The complexity of given algorithm is $\max(n, k\lg n)$. So, we can modify the algorithm only when $k \lg n > n$ or $k > n/ \lg n$. 

Find the kth largest element in array - O(n) 

After this do a linear search on the array and multiply all elements >= kth largest. So, complexity remains $O(n)$.

0
Arjun sir not able to understand your procedure well. Also CLRS says we can prepare heap in O(nlogn) time with the note that asymptotically tight bound is O(n). Was just guessing if this statement can have any effect on the solution.
0
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
@ srestha

quick select algorithm???
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,170 answers
193,841 comments
94,047 users