Time Complexity of an Algorithm (Nested Loops)

Question

I'm trying to figure out the time complexity of this pseudocode given algorithm:

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

I know that the first line runs

n times

But I'm not sure about the second line.

Okay, if I understand this correctly, if the second loop were to be j=1 to n/i, would the resulting complexity be (n*n/i) which is again O(n^2)? — Aede, Jan 15 '16 at 01:14
Oh OK my bad, forgot that! Good question btw, so I will upvote since it's your first time, but please make sure that you post the appropriate questions in the appropriate sites of Stack Exchange next time. :) — gsamaras, Jan 15 '16 at 01:21
Actually, @Aede, if the second loop was from 1 to n/i, you would be making n+n/2+n/3+...+n/n operations, and the time complexity would be n*log(n) - see https://www.wolframalpha.com/input/?i=limit+of+%28sum+from+i%3D1+to+i%3Dn+of+n%2Fi%29%2F%28n*log+n%29+as+n+goes+to+infinite — Gabriel Ilharco, Jan 15 '16 at 01:23

score 4 · Answer 1 · edited Jan 15 '16 at 01:28

4

Using Sigma notation, we can find the asymptotic bounds of your algorithm as follows:

edited Jan 15 '16 at 01:28

gsamaras

71,951
46
188
305

answered Jan 15 '16 at 01:13

dfrib

70,367
12
127
192

score 3 · Accepted Answer · edited May 23 '17 at 11:54

Here you have a simple double loop:

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

so if you count how many times the body of the loop will be executed (i.e. how many times this line of code sum = sum + 1; will be executed), you will see it's:

n*n/6 = n²/6

which in terms of big-O notation is:

O(n²)

because we do not really care for the constant term, because as n grows, the constant term makes no (big) difference if it's there or not!

When and only when you fully realize what I am saying, you can go deeper with this nice question: Big O, how do you calculate/approximate it?

However, please notice that such questions are more appropriate for the Theoretical Computer Science, rather than SO.

score 1 · Answer 3 · edited Jan 15 '16 at 01:28

1

You make n*n/6 operations, thus, the time complexity is O(n^2/6) = O(n^2).

edited Jan 15 '16 at 01:28

gsamaras

71,951
46
188
305

answered Jan 15 '16 at 01:11

Gabriel Ilharco

1,649
1
21
34

More precisely, `n * (n / 6)` operations: the complexity is the same, but the result differs. – chqrlie Jan 15 '16 at 01:18

Time Complexity of an Algorithm (Nested Loops)

3 Answers3