Algorithm time complexity (nested loops)

Question

I am trying to find out the time complexity of this pseudo-code algorithm:

sum = 0; for (i = 1; i <= n; i++) for (j = 1; j <= n / 6; j++) sum = sum + 1; 

I know the first line works

n times

But I'm not sure about the second line.

Answer 1

Here you have a simple double loop:

 for i=1;i<=n;i++ for j=1; j<=n/6; j++ 

therefore, if you calculate how many times the loop body will be executed (i.e. how many times this line of code sum = sum + 1; will be executed), you will see the following:

n * n / 6 = n² / 6

which in terms of the notation big O:

About (N²)

because we don’t care about the constant term, because when n grows, the constant term does not make a (big) difference if it is there or not!

---

When and only when you are fully aware of what I'm saying, you can better understand this pleasant question: Big O, how do you calculate / approximate it?

---

However, please note that such questions are more suitable for Theoretical Computer Science , rather than SO.

Answer 2

Using sigma notation, we can find asymptotic estimates of your algorithm as follows:

Answer 3

You are performing operations n * n / 6, so the complexity of the time is O (n ^ 2/6) = O (n ^ 2).