0

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 .

Endrit Shabani
  • 109
  • 1
  • 6
  • 2
    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 ... – meowgoesthedog 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

1 Answers1

1

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).

Miljen Mikic
  • 14,765
  • 8
  • 58
  • 66