Was asked to prove lower bound of comparison-based sorting algorithms is O(nlogn) by Google
Recently had an onsite interview at Google. During a question I was talking out loud about potential approaches and mentioned something like “even if we sorted it first we know that we can’t do better than O(nlogn).” The interviewer stopped me and asked why not, and I said because we have to do a comparison-based sort. Then he asked me if I can prove that’s the case. I think I messed up because I actually tried to prove it rather than just go back to the problem. I used some tree based method I vaguely remembered from school where you split based on if an element is larger or smaller than another then count the number of nodes or something and its nlogn. I spent about 10 minutes trying before the interviewer said in an annoyed voice it’s okay just go back to the problem. I only had 10 minutes left and I couldn’t finish it. The other interviews went decent. Should I be expected to reproduce that proof on the spot? Current TC: 180k
You should have said, I can but it will take time to work through it since it is a limitation I know from school, but in the interest of time, I think it would be best to continue on the problem at hand.
Yeah I realized this after 😔
Consider that any comparison based sorting alg works by outputting some permutation of the input as the correct “sorted” result. Initially there are n! possible permutations to output, before any comparisons are made. Now, after the first comparison is made (I.e. “is a0 < a1?”), at least half of all of the possible permutations can be eliminated, because half will have a0 > a1 and half will have a0 < a1. Likewise, at every subsequent step, the search space of all possible “output permutations” is cut in half after every comparison. This means that in the worst case, any comparison based sorting algorithm has to do log(n!) work to produce a solution. Log(n!) = log(n) + log(n-1) + ... = sum(log(i)) from i=1 to i=n, which ends up being Theta(nlogn), which means that it is also Omega(nlogn). You can verify that the summation result is correct using the integral test. Hence, nlogn is a lower bound for all comparison based sorting algorithms. That said, I only know this because I’m a graduate student studying computer science (currently taking an algorithms class), and I would absolutely in no way expect that a SWE candidate should know this during an interview.
Don't think this proof is valid. The effect of comparisons on search space is not independent. In other words, if we have that a0 < a1, a0 < a2, a0 < a3, ..., a0 < a(n-1), then a(n) < a0 case has MUCH fewer possible permutations than a0 < a(n) case. Only on the first comparison is the search space halved. After that, it varies. Edit: My edit fucked things up. The < are the less than sign.
I was taught the tree based approach. If there are n! possibilities (aka leaves) in the search tree than the average depth of all leaves cannot be less than O(nlogn).
The fuck is a comparison based sort
A sort that relies on explicitly comparing elements. For example a counting sort would not have to do that
Most likely he waa asking you to prove why sorting is a requirement, and not about sorting algorithms itself
I don’t think so since he tried giving some hints as I was trying to prove it
Could you give a justification saying something like it has to be greater than n as we have to go over each element and make comparisons. Comparing against every other element works at n^2, but making optimizations improve it. So it has to be between n and n^2, and just talk about one algorithm for example and how it helps improve from n^2. Not the complete answer but makes it conversational?
it is a CS textbook question with a CS textbook answer
If they're expecting a complete/actual math based proof, I'd think that they'd ask it as a separate question with dedicated time. Since they stopped OP in another question, they were probably looking to see how they think? I don't know though, I have limited interview experience.
Isn’t it like there are n! permutations of arrangement and O(n!) is roughly O(nlogn)
Though Im not sure if I can prove O(n!) is O(nlogn)
N! Isn’t roughly nlogn unless I’m missing something.