Finding time complexity of algorithms using big-O notation

Question

I have an answer for both but I'm not very confident in my work. Could someone please check it over and correct any mistakes?

for (i = 1; i <= n; i++) {
    for (j = 2*i; j <= n; j++) {
        puts("hello");
    }
}

My answer: 1+(N+1)+N+N[1+((N+1)+N+N[1])/2] = 3/2N^2+7/2N+2 = O(N^2)

The part where it says j=2*i really throws me off and my thought process is that after j=2*i, the rest of the code only executes half as much since it will surpass N twice as fast compared to the case if j were equal to i.

for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
        for (k = 1; k <= 200; k++) {
            printf("%d %d\n", i, j);
        }
    }
}

My answer: 1+(N+1)+N+N[1+(N+1)+N+N[1+201+200+200[1]]] = 604N^2+4N+2 = O(N^2)

I feel like this should be O(N^3) since it's a triple nested loop, but I was also thinking it's possible for it to be O(N^2) because the very last loop goes around 200 times, not N times.

How did you come up with `1+(N+1)+N+N[1+((N+1)+N+N[1])/2]`? In cases like these you typically count the number of times the inner loop `j` runs for each value of the outer loop `i`, and that just gives you a single series of values, e.g. [1+2+3+...+(N-1)+N = N*(N+1)/2 = O(N^2)](https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop) (in this case it's 2+4+..., but the basic idea is the same). — Bernhard Barker, Jan 28 '18 at 00:56
Well I basically found the values for every section of the code, so i=1 is 1, i<=n is N+1, i++ is N, then i multiply the inside loop by the number of times the previous loop invokes it, which is N, and then I repeat. — Spectre, Jan 28 '18 at 21:09

score 1 · Accepted Answer · answered Jan 27 '18 at 23:58

1

My answer [is] O(N²)

This is correct. j = 2*i initialization skips to twice the first index, but the nested loop still goes by 1 for an overall N² complexity.

Your second answer is correct as well. Although the third nested loop adds 200 iterations, this number is a constant, so it gets "factored out" from big-O asymptotic complexity result.

answered Jan 27 '18 at 23:58

Sergey Kalinichenko

714,442
84
1,110
1,523

1

So all of my work is also correct? You don't have to bother checking the simplification, just the setup. – Spectre Jan 28 '18 at 00:07

Finding time complexity of algorithms using big-O notation

1 Answers1