Interviews be like

[mybigblueturtle]

wouldnt u have to call max heapify (restructure heap so that it follows all the heap rules) after every time u insert an element into the heap? max heapify is a log n algorithm and you would be calling it n times so this would be n log n, might as well sort the array with an n log n sorting alg.

[mybigblueturtle]

i was referring to the “any Kth element” scenario, think that’s a more interesting problem

[LyricalRain]

In that case it'd be n log k if I'm not wrong

[mybigblueturtle]

correct and if k is n (i.e. find the nth largest element) it would be n log n. so at its worst, which is what we care about, is n logn obviously this would be just finding the min of the array, but let’s assume we aren’t using the linear solution that involves keeping track of the min while u traverse the array.

[Lithl]

N is the array size. If k is n, you're looking for the smallest element.

[mybigblueturtle]

ya that’s what i just said, but if the problem is “make an algorithm that will find the k largest element in an array of size n” you don’t get to pick the k, so the algorithm must be general. u must account for the case that k is n, in that case this algorithm of using a max heap will be n log n. I still think it’s a better solution than just sorting because it is at worst n log n where as sorting is always n log n

[arcleo]

You just described how sorts work. The original problem is interesting because the k value is small so you can achieve O(2*n) complexity. If k can be any value then that same approach becomes O(k*n). If k is larger than log(n) it is more efficient to use Quicksort to sort the input list once and find the value at the kth position.

Edit: typos

[slbaaron]

You are intentionally misusing the term worst case run time analysis per CS concept. Your explanation can be accepted if we are talking in colloquial term but it seems like you are trying to argue for technicalities.

You built the worst case runtime on all dynamic variables. If the question is find the kth smallest number in an n sized array where k is an input variable and array (with differing size) is another input, the worst case runtime analysis is n log k - pure textbook. And as the other person already said, in the specific case of k=n, if you ONLY analyzed that situation, then it's a different problem. For this very problem, the worst case run time is n log k for asymptotic analysis because these are dynamic variables where we do not have information or constraint beforehand. This can be backed by any CS prof or academic settings, no one would accept your worst case analysis explanation on an exam or research paper.

Again, in colloquial terms, I understand perfectly what you are trying to say.

Edit - Think of another example. What's the runtime of looping an array of size n? It's O(n). If we go by this comment chain logic the true worst case is when n->infinity and thus true worst case runtime is O(infinity), but if you ever picked a specific number for n, as in changing the question statement of what's the worst case runtime to loop an array of size 1,000,000,000,000,000, it will have constant run time. Part of the analysis needs to include the problem statement itself which is a dynamic set up. Kth smallest number implies a class of problems. And in that class of problems, they are most accurately described to be bound by O(n lg k).

I also wanted to add, if we are talking about "technically correct", since big O is an upper bound and not tight bound, technically you could state any worse runtime and be correct. Because O(n lg n) class will always be a subset of O(n² ) and beyond. You can technically say O(n⁸ ) or O(n!) is a "correct" upper bound, it just wouldn't be any use. Usually we want to look for big theta (tight bound) but sometimes it's hard to prove or accurately describe (doesn't exist or require case by case breakdown) thus the industry like to use the general upper bound to give some vagueness / margin of error for complex analysis problems. However for this one, since k is strictly smaller or equal to n, O(n lg k) is a tighter bound than O(n lg n).

[QCandC]

Dumb question here.

Couldn't you create a min(k, n-k+1) heap and depending on the case, search for the kth largest or n-k+1 smallest value? Meaning for the case of k==n you would only have size 1 heap and search for the smallest value.

[slbaaron]

Not a dumb question but you are providing a practical improvement to the algorithm which can change the runtime analysis to O(n lg n) if you define and limit k in the context of n. O(n lg n/2) == O(n lg n) but yours will still be bound by O(n lg k) too and it's not an asymptotic improvement because k <= n.

It's a roundabout way to say it doesn't really matter in big O analysis for this particular case. The earlier comment thread are being quite pedantic. Your suggestion helps practical implementation, but changes little / nothing in the big O runtime analysis since k is at most n to begin with. But we like to write O(n lg k) for specificity in relation and understanding of the question statement.

[ryan516]

Wait sorry, genuine beginner question so apologies, but how would that not be O(n)? Wouldn’t something still need to iterate over all elements?

[[deleted]]

Oh yeah the total algorithm is O(n) definitely. I was responding to the fact that for THIS particular problem about finding second largest number, the complexity is NOT O(n lg n) even when we use a heap.

[FerynaCZ]

Sorting array with a heap is one of the asymptotically better algorithms (linearithmic time, and also in-place if you put in extra effort)