time complexity of two nested loops [duplicate]

Question

I'm studying algorithms and I've met a problem, that I can't solve.

for(int i = 0; i < n; i++)
    for( int j = 0; j < i; j++)
        sum++;

So, time complexity of this code is n^2. But. First loop is iterating n times and I understand that. But second one is iterating n(n+1)/2. So.. It becomes n*(n(n+1))/2. Where I went wrong?

The second one is not iterating n(n+1)/2. If i is 100, it's not going to increment sum 4950 times. — Mooing Duck
– Mooing Duck, Commented Dec 6, 2017 at 18:17

Luai Ghunim · Accepted Answer · 2017-12-06 22:48:15Z

3

First thing you need to understand Big-O notation. It throws all lower order terms and keeps only the highest N.

Your outer loop runs N times ,so the highest term is n and what is the highest value for inner loop? It's (n-1).

So for Nth iteration of outer loop, you get n-1 iteration for inner loop which is N(N-1) = (N^2 - N) and with big-O it's O(N^2)

edited Dec 6, 2017 at 22:48

answered Dec 6, 2017 at 18:21

Luai Ghunim

9767 silver badges15 bronze badges

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

1 Comment

Leo Odishvili Over a year ago

Thank you, I realized my mistake right away

Collectives™ on Stack Overflow

time complexity of two nested loops [duplicate]

1 Answer 1

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Linked

Related