2

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;
}
dododoo
  • 21
  • 1
  • Does this answer your question? [How can I find the time complexity of an algorithm?](https://stackoverflow.com/questions/11032015/how-can-i-find-the-time-complexity-of-an-algorithm) – Oleg Ushakov May 05 '22 at 10:59
  • `O(x * 100 * CostOfPushToStack) = O(x * CostOfPushToStack)`. Assuming `push to stack` only costs `1`, then the complexity is `O(x)`. – Zakk May 08 '22 at 10:39

2 Answers2

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.

Amadan
  • 191,408
  • 23
  • 240
  • 301
  • 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 – dododoo May 04 '22 at 23:31
  • 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)`. – Amadan May 04 '22 at 23:34
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).

Ashwin Ganesan
  • 331
  • 1
  • 4