How to prove time complexity for this algo?

Question

I have an intuition that this algorithm should have o(n) time complexity but I cannot prove it rigorously.

The question is as follows: Suppose you have an n×n 2-dimensional array A such that each row of the matrix consists of some number of 0s followed by some number of 1s. Describe a method for finding the row with the maximum number of 1s in it. What is the running time of your method? Is it possible to do it in o(n) time? If yes, prove it.

My approach:

The pseudocode is as follows: considering a 0-indexed array

col=n-1
while(a[0][col]!=0 and col>=0) col--;
for row in 1...n:
    while(a[row][col]!=0 and col>=0) col--;
    if(col==0) break;

Now I can say that from the perspective of moving along column, we are moving only O(n) steps, so complexity is O(n). But I cannot prove it properly. Please help.

Answer 1

Your intuition is a great starting point. To formalize this, consider denoting by $F(n)$ the number of times the col-- happens, or equivalently, the total time you waste in the while loops.

Notice, that col starts with the value of $n$, and can go down to up to $0$ with "jumps" of $1$. Its important that we never pass $0$, since it now means the total number of times col-- can ever happen is at most $n$. Thus, $F(n)=O(n)$.

Now, consider the rest of the code. You have to account for the for loop, but notice we already counter the while loop that is in it with the value of $F(n)$, so we need to calculate the complexity only for any other operations. But clearly, they don't cost us more than $O(n)$ total, and hence we can say that the algorithm has $O(n)$ run-time.

---

I believe this should be formal enough. If you want to be even more formal, consider:

1. Actually proving that col never goes lower than $0$
2. Writing line numbers in the algorithm, and explaining the total cost of each line (using the same methods as in this proof)

Answer 2

Maybe you could show that these lines last for $O(n)$

col=n-1
while(a[0][col]!=0 and col>=0) col--;

And the following lines last for another $O(n)$

for row in 1...n:
    while(a[row][col]!=0 and col>=0) col--;
    if(col==0) break;

And $O(n) + O(n)$ is indeed $O(n)$

The perspective of moving along column is correct, where $n$ is the number of columns