Complexity of three for loops

Question

I was wondering if time complexity of the following code is O(n^3) or O(n^2)

public void firstMethod() {
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            secondMethod();
        }
    }
}

public void secondMethod(){
    for (int i = 0; i < 6; i++) {
        System.out.println("This is a test to observe complexity");
    }
}

It's constant, so `O(1)`. – Robby Cornelissen Jul 04 '22 at 06:17 — Robby Cornelissen, Jul 04 '22 at 06:17
(there is no `n` in given code) – user16320675 Jul 04 '22 at 06:50 — user16320675, Jul 04 '22 at 06:50

Chris · Accepted Answer · 2022-08-11T19:35:09.340

This is O(1) because the runtime is constant. The bounds of each loop never change, so the method's runtime will never change.

Now, had you written the following:

public void firstMethod(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            secondMethod(n);
        }
    }
}

public void secondMethod(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println("This is a test to observe complexity");
    }
}

Then firstMethod would be O(n^3) for runtime complexity.

score 0 · Answer 2 · answered Jul 04 '22 at 08:13

E.g., a runtime complexity like O(n³) means that, when varying n, the runtime increases like n³.

So, as there is no n in your code, you can vary n as much as you want, without any effect on the runtime. In fact, there is nothing variable in your code that has any effect on its runtime, meaning it is constant, and we express that as O(1).

Even a notation like O(n²) is often used in a quite sloppy way. It should always be accompanied by a clear definition what n means. But quite often, we are forced to assume that n might mean the length of an array, or the number of bits in an input number or whatever.

To sum it up:

If the runtime of your code does not depend on some variable input, you get O(1).
In the O(xyz) notation, you need to use variable names that are clearly defined.

Complexity of three for loops

2 Answers2