What is the runtime of this nested for loop?

Question

for i = 1 to n   
  for j = 1 to i - 1

Is the runtime of this O(n^2)? Is there a good way to visualize things when approaching these types of problems to find the right answer?

MBo · Accepted Answer · 2018-10-31 21:55:08Z

3

Inner loop executes

1 + 2 + 3 + 4 + 5 +...n-1 = n*(n-1)/2 times

using formula for arithmetic progression sum, so overall compexity is O(n^2)

answered Oct 31, 2018 at 21:55

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Raqib · Accepted Answer · 2018-10-31 21:47:53Z

0

Each for loop is O(n), two for loops O(n)*O(n) = O(n^2)

Check this link out. The author explains good ways to approach figuring out runtimes.

answered Oct 31, 2018 at 21:41

Raqib

1,44213 silver badges24 bronze badges