CODEWITHSUNDEEP
algorithmtime-complexitybig-o
Spectre
Spectre

Reputation: 138

Finding time complexity of algorithms using big-O notation

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.

Upvotes: 2

Views: 342

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726569

My answer [is] O(N2)

This is correct. j = 2*i initialization skips to twice the first index, but the nested loop still goes by 1 for an overall N2 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.

Upvotes: 1

Related Questions