Time complexity of nested loop?

Question

I'm not very familiar with Big O notation. I'm wondering does the time complexity of the nested loop always be n^2? For example the following function, the inner loop runs 100 times per loop, does it be considered as n times as well? What's the time complexity of this function?

int abc(int x) {
    for (int i=0; i<x; i++) {
         for (int j=0; j<100; j++) {
             push to stack;
        }
    }
    return 0;
}

Does this answer your question? How can I find the time complexity of an algorithm? — Oleg Ushakov
– Oleg Ushakov, Commented May 5, 2022 at 10:59
O(x * 100 * CostOfPushToStack) = O(x * CostOfPushToStack). Assuming push to stack only costs 1, then the complexity is O(x). — Zakk
– Zakk, Commented May 8, 2022 at 10:39

Amadan · Accepted Answer · 2022-05-04 23:10:21Z

1

Big O notation shows how the performance scales with input size. The inner loop is not at all affected by any change in input size, so it is not reflected in the time complexity: this code is O(N), where N is the size of x.

answered May 4, 2022 at 23:10

Amadan

200k23 gold badges252 silver badges321 bronze badges

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

2 Comments

dododoo Over a year ago

Thank you for answering. So if the loop is like this: int abc(int x) { for (int i=0; i<1000; i++) { int j = 0; while (j<i) { push to stack; j++; } } return 0; }. It is not affected by the input size, does the time complexity become O(1)?

Amadan Over a year ago

Yes, a double loop that does not in any way depend on input size is O(1). There is no difference in time complexity between that code and a simple sleep(1).

Ashwin Ganesan · Accepted Answer · 2022-05-08 10:25:42Z

0

If a statement is executed 100 times or 1000 times, the total cost for that statement is O(1).

In the given program, the outer loop has x iterations, and each iteration costs O(1). So the total cost is O(x).

answered May 8, 2022 at 10:25

Ashwin Ganesan

3311 silver badge4 bronze badges

Collectives™ on Stack Overflow

Time complexity of nested loop?

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related