4.1.32 : Initialising an array does not take constant time.

[SSoelvsten]

The solution to 4.1.32 is only linear-time, assuming that the statement new boolean[graph.vertices()]; takes constant time. In C++ this would indeed somewhat be the case, since bool is a trivially constructible type. Hence, one could say its just an irritating feature of Java, but a small experiment shows this indeed requires linear time in practice and hence makes the solution O(|V|²+|E|).

The solution for Java would be to initialise it only once, and reuse space with a clear() function. By doubling the amount of space, we can keep track of whether a value is a value of a prior clear() iteration. Here is an untested sketch of this idea for any generic type.

public class ReusableArray<T> {
  private int number_of_clears = 0;
  private int[] latest_clear; // <-- initialized to '0'
  private T[] values;         // <-- initialized to 'null'

  public ReusableArray<T>(int N) {
    latest_clear = new int[N];
    values = new T[N];

    for (int i = 0; i < N; ++i)
      latest_clear[i] = -1; // <-- changing the logic slightly, we could skip this.
  }

  public boolean has(int i) {
    return latest_clear[i] == number_of_clears;
  }

  public T get(int i) {
    return has(i) ? values[i] : null;
  }

  public void set(int i, T t) {
    latest_clear[i] = number_of_clears;
    values[i] = t;
  }

  public void clear() {
    number_of_clears += 1;
  }
}

In fact, since 4.1.32 only cares about booleans, one can remove the value array and only use the latest_clear array to see whether a value was set to true.

[reneargento]

You are right, the solution is not linear if we initialize the array on every iteration.
Your idea of a reusable array is nice and it works, but adding a new ReusableArray data structure might make the solution a bit more complex than it needs to be.
I updated the exercise with a simple array, based on your idea: e927b3c
Thanks for the contribution!

[SSoelvsten]

Thank you for such a great resource. 🙂