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

It is O(n^2) cause total numer of iterations is approximately n*(n-1)/2 — DollarAkshay
– DollarAkshay, Commented May 17, 2016 at 23:20
No, How will iterate just once ? It will iterate till n. So if i+1=2 and n=100 it will iterate 98 times — DollarAkshay
– DollarAkshay, Commented May 17, 2016 at 23:26

T. Claverie · Accepted Answer · 2016-05-17 23:46:26Z

3

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

edited May 17, 2016 at 23:46

answered May 17, 2016 at 23:30

T. Claverie

12.4k1 gold badge19 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

user3667111 Over a year ago

Why do you give the formula which gives the result of the previous?

T. Claverie Over a year ago

Thanks for pointing out the mistake, I edited the post and forgot to update a part.

user3667111 Over a year ago

so how do you get n*(n+1)/2 from n + n-1 + n-2?

T. Claverie Over a year ago

I edited the post. Tell me if something isn't clear.

Paul Hankin Over a year ago

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.

Collectives™ on Stack Overflow

Algorithms complexity analysis

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related