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) (in this case it's 2+4+..., but the basic idea is the same). — Bernhard Barker
– Bernhard Barker, Commented Jan 28, 2018 at 0: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
– Spectre, Commented Jan 28, 2018 at 21:09

Sergey Kalinichenko · Accepted Answer · 2018-01-27 23:58:44Z

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, 2018 at 23:58

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

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

1 Comment

Spectre Over a year ago

So all of my work is also correct? You don't have to bother checking the simplification, just the setup.

Collectives™ on Stack Overflow

Finding time complexity of algorithms using big-O notation

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related