'N' is the number of rows. It is defined in the problem statement:

Given an N * N matrix...

The reason why I am asking is For binary search solution: For a given matrix: [1,5,9] [10,11,13] [12,13,15]

The first iteration: low = 1, hight = 15 For middle value = 1+15/ 2= 8 in countLessEqual() function:

We search 12,10,1,5, and then stop at 9. (A total of 5 iter...

high* and not hight*

It takes O(N) for counting, the number of iterations is not 'N'. As the explanation says:

The Binary Search could take O(log(max-min)) iterations where ‘max’ is the largest and ‘min’ is the smallest element in the matrix.

Let me clarify further. I am not referring to the binary search component. More concerned about the counting part. I still see that it takes more than N (number of rows) times to count and find the elements lower than or higher than the middle value. (5 vs 3 in the exam...

Got it. You are right when you say that it takes more than 'N' iterations.

At max it can take 2N iterations.

But since we are talking asymptotically here, we say it takes O(N) as O(2N) => O(N).

Why it takes 2N, because in each iteration either we decrement the row or...

Okay got it, 2N and then asymptotically 0(N) makes total sense. Perfect thank you very much! I checked CTCI book, leetcode discussions and didnt understand the logic why it was 0(N) for counting. This helped.