educative.io

Educative

How we calculated run time of inner loop

how did the inner loop runs n(n-1)/2 times, can anyone please explain me


Type your question above this line.

Course: https://www.educative.io/collection/5642554087309312/5634727314718720
Lesson: https://www.educative.io/collection/page/5642554087309312/5634727314718720/5720532372684800

Hello @Sumit_Dwivedi

Let us understand this question with the help of an example. Let’s assume n = 5. This means i will run 4 times i.e. for 0, 1, 2, 3, and 4. Now when i = 0, inner loop will not execute at all. For i = 1, inner loop will execute 1 time. For i = 2, inner loop will execute for 2 times. For i = 3, inner loop will execute for 3 times. So we can see a pattern over here. So for i = n, inner loop will execute for 0 + 1 + 2 + 3 + … + (n - 1) times. The sum of this series equals to n(n - 1)/2.

Hope this helps!