# How to prove time complexity for this algo?

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.

• Please credit the original source for the task you're working on. We require proper attribution for all copied material, as per our policy: cs.stackexchange.com/help/referencing
– D.W.
Sep 6, 2021 at 20:54
• okay sure, but it is actually one of the class questions we were asked to work on as part of exam content in our current cs course. So do i need to mention this?
– Alex
Sep 6, 2021 at 21:46
• (Please make sure to write what you intend: It is very easy to meet a lower bound on time such as $o(n)$.) Sep 7, 2021 at 4:31
• When something is just too obvious, try by contradiction. When something is trivial for a trivial case, and not harder for "one more", try induction. Sep 7, 2021 at 4:34
• I think it will be more clear if you tried to demonstrate by drawing like a cursor movement in an example, the main point that in each step you need to make only 1 move either row or column to scan the whole array; ie worst case is 2n or 2n-1 or 2n-2 I you check the exact value
– ShAr
Sep 10, 2021 at 10:47

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)
• umm.. like it seems good but still our prof is kinda rigorous on proving stuff.
– Alex
Sep 6, 2021 at 21:49
• Proving rigorous stuff on algorithms isn't as easy. Usually, there is some accepted base assumption - like that here the run-time can be measured by checking the number of times each operation happens. Sep 6, 2021 at 22:12

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