0

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?

Leo Odishvili
  • 1,004
  • 1
  • 7
  • 29

1 Answers1

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)

Luai Ghunim
  • 976
  • 7
  • 14