# Finding largest elements

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

largestLogn(Arr)

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]
j++

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.

• 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)$. – Yuval Filmus Apr 26 at 7:03
• Does this answer your question? cs.stackexchange.com/questions/139451/… – Nathaniel Apr 26 at 7:03
• @YuvalFilmus We've just started talking about data structures and haven't covered selection algorithms! So I can't really use it.. – MathCurious Apr 26 at 7:33
• @Nathaniel I guess my question was if my solution was flawed, and if so then where therefore other solutions don't really help me.. – MathCurious Apr 26 at 7:34
• Does this answer your question? Finding an algorithm to return the $\log n$ largest element in an array – 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)$$.

• Nice! It works better than my solution plus it somewhat resembles the hint. Thanks! :) – 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).

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

‌ Below method, solve your problem in $$\mathcal{O}(n)$$, and additional space $$\mathcal{O}(n)$$.

Use Selection algorithm to find $$(\log n)^{th}$$ largest element in worst case $$\mathcal{O}(n)$$.

Then your array become below form :

That we partition the array in term of $$(\log n)^{th}$$ largest element. Now all elements in $$L$$ are greater equal to $$(\log n)^{th}$$ largest element. On the other hand, all elements in $$R$$ are smaller than $$(\log n)^{th}$$ largest element, so we can discard $$R$$. now we have $$\lg n$$ largest elements that can be sorted in camparision model in $$\mathcal{O}(\log n\log\log n)$$ by algorithm such as merge sort. But because we need $$\mathcal{O}(n)$$ to partition the array, So the term $$\mathcal{O}(n)$$ dominate other terms and the running time is $$\mathcal{O}(n)$$ that is better than your idea in large datasets, but for small datasets, it has constant factor that maybe not worth.

Note that, the lower bound for solving you problem is $$\Omega(n)$$ because we need at least once read all $$n$$ elements, so you can't do better.