CODEWITHSUNDEEP
loopsbig-o
stumped
stumped

Reputation: 3293

(Big O) Finding the number of iterations in a nested loop

By this logic why are there n(n-1)/2 iterations for the inner loop? If the sum of 1 to N results in n/2*(n+1), then why doesn't the sum of 1 to N-1 result in n/2*(n)?

enter image description here

Upvotes: 0

Views: 80

Answers (2)

John Kugelman
John Kugelman

Reputation: 361984

Subtract 1 from both occurrences of n. n×(n+1)/2 decreases to (n-1)×(n+1-1)/2 which equals (n-1)×n/2. Swap the two terms and you have n×(n-1)/2.

Upvotes: 1

xrisk
xrisk

Reputation: 3898

The sum of integers from 1...N = N*(N+1)/2.

Therefore the sum of integers from 1...(N-1) = (N-1)*(N)/2 and not N/2*N as you claim.

Either way, the big-O remains O(n^2).

Upvotes: 0

Related Questions