How to prove time complexity for this algo?

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)