Algorithms complexity analysis

Question

I'm new here so cut my some slack and let me know if my question can have any improvements.

So me and a friend are at a bit of a disagreement on an algorithm's complexity. He seems to be certain that the algorithm has a big O notation of O(n^2) but I just think its O(n)

Can we have some pointers, to hopefully end our argument ha!

The Algorithm:

Input: Matrix M[1..n][1..n]
Output: boolean true if M is lower triangular
begin isLowerTriangular(Matrix[][] M, size n)
 for i:=1 to n-1 loop
 for j:=i+1 to n loop
 if M[i][j] != 0
 return false
 return true
end isLowerTriangular

• DollarAkshay: It is O(n^2) cause total numer of iterations is approximately n*(n-1)/2
• DollarAkshay: No, How will iterate just once ? It will iterate till n. So if i+1=2 and n=100 it will iterate 98 times

Answer 1

It's O(n^2).

for i:=1 to n-1 loop
 for j:=i+1 to n loop
 operation()
 done
done

So, for i = 1, the second loop is executed n times, for i = 2 it is executed n-1 times, etc..

This gives the sum n + n-1 + n-2 + ... + 1 The formula which gives the number of operation() ran is n*(n+1)/2 or (n^2 + n)/2.

Thus, it's O(n^2)

EDIT:

Get the formula

The trick to get the result is to add what I call the reverse sum, that is the same sum in reverse order. Here is how it works:

We want to compute 1 + 2 + 3 + ... + n-2 + n-1 + n
For this, we add n + n-1 + n-2 + ... + 3 + 2 + 1
(we remember that we have to divide by two after).
We pair the operands of those two sums now:
 1 + 2 + 3 + ... + n-2 + n-1 + n
+ n + n-1 + n-2 + ... + 3 + 2 + 1
= n+1 + n+1 + n+1 + ... + n+1 + n+1 + n+1
= n * n+1
To get this, we just added together 1 and n, then 2 and n-1, ...
Remember that we have to divide by 2, and we get the final result:
1 + 2 + 3 + ... + n-2 + n-1 + n = (n * n+1)/2

• user3667111: Why do you give the formula which gives the result of the previous?
• T. Claverie: Thanks for pointing out the mistake, I edited the post and forgot to update a part.
• user3667111: so how do you get n*(n+1)/2 from n + n-1 + n-2?
• T. Claverie: I edited the post. Tell me if something isn't clear.
• Paul Hankin: In this case, one doesn't need much maths -- the code looks at every below-diagonal element in the matrix. There's n^2 things in the matrix, and n on the diagonal, and half of the remaining elements are below the diagonal (the other half above). So (n^2 - n)/2. This differs from the formula in your answer: you're off by one (when i=1, j goes from 2 to n, so the loop code is executed n-1 (not n) times.