// Assert that the dataset contains the same elements after the in-place computation (although
    // they may be reordered). We only do this for one index rather than for all indexes, as it is
    // quite expensive (quadratic in the size of PSEUDORANDOM_DATASET).
    double[] dataset = Doubles.toArray(PSEUDORANDOM_DATASET);
    @SuppressWarnings("unused")
    double actual = percentiles().index(33).computeInPlace(dataset);

 *
 * <h3>Performance</h3>
 *
 * <p>The average time complexity of the computation is O(N) in the size of the dataset. There is a
 * worst case time complexity of O(N^2). You are extremely unlikely to hit this quadratic case on
 * randomly ordered data (the probability decreases faster than exponentially in N), but if you are
 * passing in unsanitized user data then a malicious user could force it. A light shuffle of the

    }
    for (int j = 0; j < 1000; j++) {
      builder.add(9);
    }
    ImmutableSortedSet<Integer> unused = builder.build();
    assertThat(compares[0]).isAtMost(10000);
    // hopefully something quadratic would have more digits
  }

  public static <E extends @Nullable Object> CopyOnWriteArrayList<E> newCopyOnWriteArrayList(
      Iterable<? extends E> elements) {
    // We copy elements to an ArrayList first, rather than incurring the
    // quadratic cost of adding them to the COWAL directly.
    Collection<? extends E> elementsCollection =
        (elements instanceof Collection)
            ? (Collection<? extends E>) elements
            : newArrayList(elements);