Какова производительность при вызове get (Range) по отношению к размеру диапазонов? Зачем?

Question

Я хочу знать значение Big O этого кода для метода get (Range) для диапазонов

Я думаю, что это должно быть O (N) N-> диапазонов значений до 1 ... N

Range get(Range r) {
  Range lower = ranges.lower(r);
  Range higher = ranges.higher(r);
  if (ranges.contains(r)) {
    return r;
  }
  if (lower != null && lower.end >= r.start) {
    return lower;
  }
  if (higher != null && higher.start <= r.end) {
    return higher;
  }
  return null;
}

Answer 1

Если ranges.contains реализовано в O(f(n)), время выполнения вашего алгоритма равно O(f(n)).Потому что другие ограничения будут проверяться в O(1), и каждый диапазон здесь определяется двумя целыми числами.