The numbers are stored in a matrix and using 2 levels of for-loop for doing the job, so why the time complexity is still O(n)?
1 Like
@weiwei I also was confused by this fact, but I think that’s because we have a 2D matrix as an input (which has n elements in it) and therefore, even though we do 2 inner loops, we iterate over all input elements only once. We don’t iterate n * n times.
2 Likes
why cant we ~ it (bitwise not) instead of xor?
Because n = total number of digits and you visit each digit once. If n = size of a square matrix side, the complexity would be O(n * n).
Becuase even though there are two loops, the inner loop only traverses 1/2 the elements since it is swapping at both ends of the array.
So it would appears it is O(n * log n), but worst case you get a 1 x n ([[1],[1],[1],…[n]]) you’d have to traverse all elemnts (n).
So the run time is O(n)