I was asked to find write a pseudocode of an algorithm that extracts the Log(N) largest elements in an array and return them in a sorted list, my attempt is


n = Arr.length
j = 0
ans = new array of size Log(n)

Arr = Quicksort(Arr,1,a)

for i=(a-log(n)) ➜ a
ans[j] = Arr[i]

return ans

From my limited understanding, the time complexity of this algorithm is $O(n\log n)$ for the QuickSort and $O(\log n)$ for the loop but in the question they hinted that the time complexity has something to do with the fact that $(\log(n))^{a}=O(n^{b})$ for any $a,b>0$ and now I'm not sure of my answer.

  • 2
    $\begingroup$ You can improve the running time to $O(n)$ using linear time selection to find the $(\log n)$-th largest element, after which you extract the $\log n$ largest elements, which you can sort in $o(n)$. $\endgroup$ – Yuval Filmus Apr 26 at 7:03
  • 1
    $\begingroup$ Does this answer your question? cs.stackexchange.com/questions/139451/… $\endgroup$ – Nathaniel Apr 26 at 7:03
  • $\begingroup$ @YuvalFilmus We've just started talking about data structures and haven't covered selection algorithms! So I can't really use it.. $\endgroup$ – MathCurious Apr 26 at 7:33
  • $\begingroup$ @Nathaniel I guess my question was if my solution was flawed, and if so then where therefore other solutions don't really help me.. $\endgroup$ – MathCurious Apr 26 at 7:34
  • 2
    $\begingroup$ Does this answer your question? Finding an algorithm to return the $\log n$ largest element in an array $\endgroup$ – Ran G. Apr 28 at 17:41

The second loop in your solution requires time $O(\log n)$ and can be safely ignored since its time complexity is dominated by the previous sorting step.

The call to Quicksort requires time $O(n \log n)$ in expectation and $O(n^2)$ in the worst case.

You can solve your problem in $O(n)$ worst-case time as follows: create a max-heap with the elements in the array. Then, perform $\log n$ extract-max operations. Creating the heap takes $O(n)$ time while each of the maximum extractions requires $O(\log n)$ time, for a total time of $O(n + \log^2 n) = O(n)$.

  • $\begingroup$ Nice! It works better than my solution plus it somewhat resembles the hint. Thanks! :) $\endgroup$ – MathCurious Apr 26 at 7:34

Assume the array elements are in random order. Create a sorted array of size log n. Insert the first log n items. Then insert the next elements if they are larger than the smallest element in that array.

Estimate how often the k-th element of a random array is within the (log n) largest elements so far, and how much work is done in that case. You’ll find the total time for this is quite small and the total time is O(n).

  • $\begingroup$ Estimate how often [you actually insert] unfavourably often, worst case. $\endgroup$ – greybeard Apr 26 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.