How to calculate big O notation for this nested loop?

Question

if I have for example this simple code

for (i =1;i<=n;i++)
for (j=1 ;j<=i;j++)
   count++;

for this line

for (i =1;i<=n;i++)

if I say that the time for 'i' to get a value is T then i will increase n+1 times since the condition is i<=n so the time for increasing i is (n+1)*T the condition will be asked n+1 times so lets say that the time needed to check the condition is T aswell then the total time for it to complete is (n+1)*T and i++ will be executed n times because when the condition is asked if i(in this case i is n+1) <=n it will be false so it wont increase i so the total time for executing this single loop would be (n+1)*T+(n+1)T+nT or (n+1+n+1+n)*T = (3n+2)T so big O for this case would be n but I dont know how to calculate for the second loop I was thinking if it would be n[(3n+2)*T] and big O for this would be n^2 but I am not too sure if you dont understand what I am saying or if I made a mistake with first loop too if you can please explain in details how to I calculate it for that code .

Possible duplicate of [Big O notation for triangular numbers?](https://stackoverflow.com/questions/3179338/big-o-notation-for-triangular-numbers) — jimboweb, Mar 05 '18 at 20:15
If we had a penny for every time this *exact* piece of code has been posted without researching first ... — willywonkadailyblah, Mar 05 '18 at 21:26
if I had a penny for everytime people commented something not related to the question I would .... — Endrit Shabani, Mar 06 '18 at 11:01

score 1 · Accepted Answer · answered Mar 05 '18 at 20:18

First loop will execute n times, second loop i times, for each i from the outer loop. At the beginning, i=1, so the inner loop will have only one iteration, then i=2, i=3.. until i reaches the value n. Therefore, the total number of iterations is 1 + 2 + 3 + ... + n = n * (n + 1) / 2, which gives O(n^2).

How to calculate big O notation for this nested loop?

1 Answers1