How is time complexity calculated for inner loops?

Question

I have this code to analyse:

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        System.out.println(j);
    }
}

What is the time complexity of this code?

Assuming n=10:

For every iteration of the outer loop, the inner loop runs n times, i.e. 10*10 = 100 times. Whereas the outer loop runs n times, i.e. 10 times. So isn't the time complexity O(n)*O(n²)=O(n³)? I see it as O(n²).

Answer 1

I see it as O(n²).

O(𝑛²) would be correct (but see below for a nuance).

It is true that the outer loop has 𝑛 iterations, but if you already count 𝑛² for the total of inner loop iterations, then it is an addition, not a multiplication. So with this approach you could say it is O(𝑛 + 𝑛²), which is O(𝑛²).

But the situation is complicated by the printing of the number. If we just gloss over that, and consider that printing a number has O(1) time complexity, then we are done. But fact is that the printing effort is determined by the number of characters to print. To print a number with five digits takes longer than printing a number with just one.

The number of digits in a number 𝑛 is O(log𝑛), and thus the time complexity of the print call is O(log𝑗). In total we thus have O(𝑛(log1 + log2 + ... + log𝑛)) which is O(𝑛(𝑛log𝑛)), which is O(𝑛²log𝑛).