I think you saw the 2nd case before I correct it to make my point clearer. In the first example, it is O(N^2) with clock cycles but O(N) with memory access. I

I think you saw the 2nd case before I correct it to make my point clearer. 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).