Space complexity of the piece of code below?

Question

I came across this question while I was doing some interview prep.

public class Main {
    public static void main(String[] args) {
        // n is some user input value
        int i = 0;
        while (i < n) {
            int[] a = new int[n];
            for (int j = 0; j < n; j++){
                a[j] = i * j;
            }
            i++;
        }
    }
}

The choices given were:

1. O(n)
2. O(n^2)

From what I understand the answer should have been O(n) as on every iteration a new instance of the array is being created and the previous reference is being lost. However, the book mentions the answer to be O(n^2).

What could be a possible explanation?

Answer 1

Explanation

Your explanation is correct. The space complexity is linear.

However, your conclusion (and the conclusion of the books author) is wrong. The correct answer is that both answers are correct. That is, the space complexity is in both:

• O(n) and
• O(n^2)

Big-O gives an upper-bound, not the exact bound. Think about it as <= as opposed to just =. So if a in O(n) it is also true that a in O(n^2) (mathematically, Big-O gives a set of functions).

The exact bound is given by Theta (=) and a lower bound by Omega (>=), a strict lower bound is given by small-omega (>) and a strict upper bound by small-o (<). So the space complexity is in Theta(n).

See Wikipedia for more information and the actual mathematical definitions.

---

Notes

The space complexity is only linear if we assume that Javas garbage collector is active. It is possible to disable it or replace it by a mock implementation which does not actually free memory (see the Epsilon-GC).

In that case, the space complexity would indeed be quadratic.

The algorithm itself needs to allocate a quadratic amount of memory. However, it will only ever hold a linear amount of memory at the same time. Space complexity analysis is typically done with respect to how much memory must be hold at the same time. But maybe the author wanted to analyze the algorithm with respect to how much needs to be allocated in total, which could also explain his choice.

Answer 2

The book seems to simply have it wrong. The required space to execute is O(n). As to the possible explanation: the author had runtime complexity in mind. The nested loop gives a O(n^2) runtime complexity. If the book is somewhat recent and popular, it may have an errata webpage, which might shed light on it.