What to do? Technical interview where interviewer stubbornly gets Big-O wrong.
reddit.com
reddit.com
The tactical error the interviewee made was not addressing the misconception on a different play field and then misplaying the politics (assuming he wanted the job). He should have brought the question up in each subsequent interview and seen the reaction of the organization.
The way to address the misconception is to pose a slightly different question of the interviewer, namely, is this O(N) or O(N^2):
for (i=0; i<N; i++) { for (j=0; j<N; j++) { if (i==j) maxtrix[i,j] = 1; } }
and this
for (i=0; i<N; i++) { for (j=i; j<=i; j++) { matrix[i,j] = 1; } }
What is going on in the story is more a case of for(i=0; i<N; i++){for (j=0; j<K(i); j++) {matrix[i,j]=1}}, where K(i) does not grow with the size of the problem; and (for the sake of Big-O analysis) can be replaced with a constant.
In the first example, it is O(N^2) with clock cycles but O(N) with memory access. If memory access is 100 times slower than CPU or your compiler is smart enough, then the O(N) term dominates.
My corrected 2nd example is clearly O(N).
The reason for presenting these example to the interviewer is to reframe the problem into something simpler to make the point that having two nested loops does not make something O(N^2).